Šajā apmācībā jūs uzzināsiet, kas ir blakus esošais saraksts. Jūs atradīsit arī blakus esošu sarakstu piemērus C, C ++, Java un Python.
Blakus esošais saraksts attēlo diagrammu kā saistītu sarakstu masīvu.
Masīva indekss apzīmē virsotni, un katrs elements saistītajā sarakstā apzīmē citas virsotnes, kas veido malu ar virsotni.
Blakusparādību saraksta attēlojums
Grafiks un tā ekvivalents blakusnodokļu saraksta attēlojums ir parādīts zemāk.
Blakusparādību saraksta attēlojums
Blakus esošais saraksts ir efektīvs uzglabāšanas ziņā, jo mums ir jāuzglabā tikai malu vērtības. Retam grafikam ar miljoniem virsotņu un malu tas var nozīmēt daudz ietaupītas vietas.
Blakusparādību saraksta struktūra
Visvienkāršākajam blakus esošajam sarakstam ir nepieciešama mezglu datu struktūra virsotnes glabāšanai un diagrammas datu struktūra mezglu organizēšanai.
Mēs paliekam tuvu grafika pamatdefinīcijai - virsotņu un malu kolekcijai (V, E). Vienkāršības labad mēs izmantojam apzīmētu grafiku pretstatā iezīmētajam, ti, virsotnes identificē pēc to indeksiem 0,1,2,3.
Iepazīsimies ar šeit spēlētajām datu struktūrām.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Neļaujiet struct node** adjListstevi pārņemt.
Viss, ko mēs sakām, ir tas, ka mēs vēlamies saglabāt rādītāju struct node*. Tas ir tāpēc, ka mēs nezinām, cik virsotņu būs diagrammā, un tāpēc apkopošanas laikā mēs nevaram izveidot saistīto sarakstu masīvu.
Blakusparādību saraksts C ++
Tā ir tā pati struktūra, taču, izmantojot C ++ iebūvēto sarakstu STL datu struktūras, mēs struktūru padarām mazliet tīrāku. Mēs varam arī abstraktēt ieviešanas detaļas.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Mēs izmantojam Java kolekcijas, lai saglabātu saistīto sarakstu masīvu.
class Graph ( private int numVertices; private LinkedList adjLists(); )
LinkedList veidu nosaka tas, kādus datus vēlaties tajā saglabāt. Atzīmētam grafikam veselu skaitļu vietā varat saglabāt vārdnīcu
Adjacency List Python
Ir iemesls, kāpēc Python saņem tik daudz mīlestības. Vienkārša virsotņu un tās malu vārdnīca ir pietiekams grafika attēlojums. Jūs varat padarīt virsotni tik sarežģītu, cik vēlaties.
graph = ('A': set(('B', 'C')), 'B': set(('A', 'D', 'E')), 'C': set(('A', 'F')), 'D': set(('B')), 'E': set(('B', 'F')), 'F': set(('C', 'E')))
Python, Java un C / C ++ piemēri
Python Java C C ++ # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = (None) * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph(s) self.graph(s) = node node = AdjNode(s) node.next = self.graph(d) self.graph(d) = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph(i) while temp: print(" -> ()".format(temp.vertex), end="") temp = temp.next print(" ") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList am, int s, int d) ( am.get(s).add(d); am.get(d).add(s); ) public static void main(String() args) ( // Create the graph int V = 5; ArrayList am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); ) // Print the graph static void printGraph(ArrayList am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; ); // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create a graph struct Graph* createAGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i adjLists(i) = NULL; return graph; ) // Add edge void addEdge(struct Graph* graph, int s, int d) ( // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists(s); graph->adjLists(s) = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists(d); graph->adjLists(d) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
