Para un grafo disperso (E mucho menor que V²), ¿qué representación se prefiere?
Opciones
- Matriz de adyacencia
- Lista de adyacencia (Opción correcta)
- Matriz de pesos de aristas
- Matriz de incidencia
Respuesta
Lista de adyacencia
Por qué
Una lista de adyacencia guarda, para cada nodo, solo la lista de sus vecinos reales: O(V + E) de memoria. En Python: {"A": ["B", "C"], ...}.
Una matriz de adyacencia es una cuadrícula V × V de sí/no, que desperdicia memoria cuando casi ninguna pareja está conectada, pero comprueba '¿A está conectado con B?' en O(1).
La mayoría de los grafos reales (redes sociales, carreteras) son dispersos.
Recuerda
Grafo disperso → lista de adyacencia.