Recorrido narrado
La tabla de costos del grafo
| Representación | Memoria | ¿Existe (u, v)? | Vecinos de v |
|---|---|---|---|
| matriz de adyacencia | O(V²) | O(1) | O(V) |
| listas de adyacencia | O(V + E) | O(grado(u)) | O(grado(v)) |
Un grafo es denso si E es del orden de V² (casi todos conectados con todos), y disperso si E es mucho menor. La mayoría de los grafos reales son dispersos: redes de carreteras, redes sociales, dependencias entre paquetes.
Mira cuántas casillas de la matriz se usan en cada caso:
- Disperso: listas de adyacencia.
- Denso y pequeño, o con muchas preguntas «¿hay arista?»: matriz.
Esta ruta solo representa grafos y recorre los vecinos de un vértice. Recorrer el grafo entero, buscar caminos y demás son procedimientos: están en la ruta de Algoritmos.
Su fila en la tabla de costos
Con la condición que decide entre ellas, las dos filas del grafo en la tabla de costos de la ruta se leen así:
| Representación | memoria | ¿existe (u, v)? | vecinos de v | conviene si… |
|---|---|---|---|---|
| matriz de adyacencia | O(V²) | O(1) | O(V) | V es pequeño o el grafo es denso |
| listas de adyacencia | O(V + E) | O(grado(u)) | O(grado(v)) | el grafo es disperso |
El «O(1)» de la matriz viene con su precio: pagar V² casillas aunque casi todas estén vacías.
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.