En este tutorial, aprenderá qué es una lista de adyacencia. Además, encontrará ejemplos prácticos de listas de adyacencia en C, C ++, Java y Python.
Una lista de adyacencia representa un gráfico como una matriz de listas enlazadas.
El índice de la matriz representa un vértice y cada elemento en su lista vinculada representa los otros vértices que forman un borde con el vértice.
Representación de la lista de adyacencia
A continuación se muestra un gráfico y su representación de lista de adyacencia equivalente.
Representación de la lista de adyacencia
Una lista de adyacencia es eficiente en términos de almacenamiento porque solo necesitamos almacenar los valores para los bordes. Para un gráfico disperso con millones de vértices y aristas, esto puede significar mucho espacio ahorrado.
Estructura de lista de adyacencia
La lista de adyacencia más simple necesita una estructura de datos de nodo para almacenar un vértice y una estructura de datos de gráfico para organizar los nodos.
Nos mantenemos cerca de la definición básica de un gráfico: una colección de vértices y aristas (V, E). Para simplificar, utilizamos un gráfico sin etiquetar en lugar de uno etiquetado, es decir, los vértices se identifican por sus índices 0,1,2,3.
Profundicemos en las estructuras de datos en juego aquí.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
No dejes que struct node** adjListste abrume.
Todo lo que decimos es que queremos almacenar un puntero a struct node*. Esto se debe a que no sabemos cuántos vértices tendrá el gráfico y, por lo tanto, no podemos crear una matriz de listas vinculadas en tiempo de compilación.
Lista de adyacencia C ++
Es la misma estructura, pero al usar las estructuras de datos STL de lista incorporadas de C ++, hacemos que la estructura sea un poco más limpia. También podemos abstraer los detalles de la implementación.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Lista de adyacencia Java
Usamos colecciones de Java para almacenar la matriz de listas vinculadas.
class Graph ( private int numVertices; private LinkedList adjLists(); )
El tipo de LinkedList está determinado por los datos que desea almacenar en él. Para un gráfico etiquetado, puede almacenar un diccionario en lugar de un entero
Python de lista de adyacencia
Hay una razón por la que Python recibe tanto amor. Un diccionario simple de vértices y sus aristas es una representación suficiente de un gráfico. Puede hacer que el vértice sea tan complejo como desee.
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')))
Ejemplos de Python, Java y 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); )
