Representaciones de grafos

Vértices + aristas. Sin raíz, con ciclos permitidos. Cómo lo guardas define el costo de todo lo que sigue.

Dos representaciones, costos espejo

Mira cómo se construye un grafo

Cada arista se agrega a las listas de vecinos de ambos extremos.

Los grafos reales son dispersos → gana la lista

Grafo disperso, 4000 vértices: 437 KB (lista) vs 125 MB (matriz) → 286×. La matriz además vuelve todo recorrido O(V²) en lugar de O(V+E).

También: dirigido/no dirigido, con pesos

• Dirigido: las aristas tienen dirección (matriz asimétrica)
• Con pesos: guarda el costo con cada vecino / en la celda
• La lista de adyacencia dirigida con pesos mueve casi todo este nivel

Para llevar

Usa la lista de adyacencia por defecto — los grafos reales son dispersos. Todo algoritmo que viene es O(V+E) gracias a eso. Sigue: BFS y DFS.