Graph Representations almacenan grafos en memoria de tres formas principales: adjacency list, adjacency matrix, y edge list. La elección afecta directamente la complejidad de los algoritmos.
Un grafo G = (V, E) con V vértices y E aristas puede representarse de forma muy distinta según la densidad.
Cómo Funciona
Adjacency List
Array de listas: adj[u] contiene todos los vecinos de u.
adj = [[1, 2], [0, 3], [0], [1]] # grafo: 0-1, 0-2, 1-3Adjacency Matrix
Matriz V×V: matrix[u][v] = 1 si hay arista u-v.
matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0]
]Edge List
Array de aristas: edges = [[0,1], [0,2], [1,3]].
Idea Clave
La elección depende del grafo y el algoritmo:
- Disperso (E ≈ V): adjacency list es mejor.
- Denso (E ≈ V²): adjacency matrix puede ser más simple.
- Kruskal: edge list es natural (ordena aristas).
- Floyd-Warshall: adjacency matrix es directa.
Comparación
| Representación | Espacio | Edge query | Vecinos de u | Mejor para |
|---|---|---|---|---|
| Adjacency List | O(V+E) | O(deg(u)) | O(deg(u)) | Grafos dispersos |
| Adjacency Matrix | O(V²) | O(1) | O(V) | Grafos densos, queries rápidas |
| Edge List | O(E) | O(E) | O(E) | Ordenar aristas (Kruskal) |
Casos Extremos y Trampas
- Grafo completo — E = V(V-1)/2, adjacency matrix O(V²) es igual que list O(V²).
- Grafo vacío — adjacency list O(V), matrix O(V²) desperdicia espacio.
- Directed vs undirected — matrix es simétrica para undirected; list requiere aristas en ambos sentidos.
- Weighted graphs — almacena peso en
matrix[u][v]o en objetos de arista.
Aplicaciones
- Diseño de algoritmos — elegir representación antes de implementar
- Bases de datos — grafos de relaciones, adjacency list en SQL
- Redes sociales — adjacency list para followers
- Enseñanza — base para todos los algoritmos de grafos
Trayectoria de Práctica
- Implementa un grafo con adjacency list; traza BFS y DFS.
- Convierte a adjacency matrix; compara espacio para V=100, E=500.
- Implementa Kruskal con edge list; ordena aristas.
- Implementa Floyd-Warshall con matrix.
- ¿Por qué Prim necesita adjacency list pero Kruskal prefiere edge list?