In questo tutorial imparerai cos'è un elenco di adiacenza. Inoltre, troverai esempi funzionanti di elenchi di adiacenze in C, C ++, Java e Python.
Un elenco di adiacenza rappresenta un grafico come un array di elenchi collegati.
L'indice della matrice rappresenta un vertice e ogni elemento nella sua lista collegata rappresenta gli altri vertici che formano un bordo con il vertice.
Rappresentazione della lista di adiacenza
Di seguito sono riportati un grafico e la sua rappresentazione dell'elenco di adiacenza equivalente.
Rappresentazione della lista di adiacenza
Una lista di adiacenza è efficiente in termini di archiviazione perché abbiamo solo bisogno di memorizzare i valori per i bordi. Per un grafo sparso con milioni di vertici e bordi, questo può significare molto spazio risparmiato.
Struttura dell'elenco di adiacenza
L'elenco di adiacenza più semplice richiede una struttura di dati del nodo per memorizzare un vertice e una struttura di dati del grafico per organizzare i nodi.
Restiamo vicini alla definizione di base di un grafo: una raccolta di vertici e bordi (V, E). Per semplicità, usiamo un grafo senza etichetta invece di uno etichettato, cioè i vertici sono identificati dai loro indici 0,1,2,3.
Analizziamo qui le strutture dati in gioco.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Non lasciarti struct node** adjListstravolgere.
Tutto ciò che stiamo dicendo è che vogliamo memorizzare un puntatore a struct node*. Questo perché non sappiamo quanti vertici avrà il grafo e quindi non possiamo creare un array di liste collegate in fase di compilazione.
Elenco di adiacenza C ++
È la stessa struttura ma utilizzando le strutture dati STL di elenco in-built di C ++, rendiamo la struttura un po 'più pulita. Siamo anche in grado di astrarre i dettagli dell'implementazione.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Elenco di adiacenze Java
Utilizziamo le raccolte Java per memorizzare la matrice di elenchi collegati.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Il tipo di LinkedList è determinato dai dati che desideri archiviare al suo interno. Per un grafico etichettato, puoi memorizzare un dizionario invece di un numero intero
Elenco di adiacenze Python
C'è una ragione per cui Python riceve così tanto amore. Un semplice dizionario dei vertici e dei suoi bordi è una rappresentazione sufficiente di un grafo. Puoi rendere il vertice stesso complesso quanto vuoi.
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')))
Esempi di Python, Java e C / C ++
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); )
