Facundo Uferer
El Lenguaje de los Grafos: Vértices y Aristas
Un grafo G = (V, E) modela relaciones arbitrarias sin jerarquía fija. V son los vértices o nodos; E son las aristas o conexiones.
Matriz de Adyacencia vs Lista de Adyacencia
La elección depende de la densidad del grafo. Grafos densos (|E| ≈ |V|²) prefieren matrices; grafos dispersos (|E| ≪ |V|²) optimizan memoria con listas.
| A (0) | B (1) | C (2) | D (3) |
|---|
Espacio: O(V²). Consulta de adyacencia: O(1).
Espacio: O(V + E). Consulta de adyacencia: O(grado(v)).
BFS (Breadth-First Search): La Onda Expansiva
BFS expande capa por capa desde el origen usando una Cola FIFO. Encuentra el camino mínimo en cantidad de saltos.
DFS (Depth-First Search): El Hilo de Ariadna
DFS avanza por una rama hasta topar con un callejón sin salida y luego retrocede (backtracking). Utiliza una Pila LIFO o la pila de llamadas (Call Stack).
Iniciamos en el nodo raíz A
Algoritmo de Dijkstra: Relajación con PriorityQueue
Calcula la distancia mínima desde un nodo origen a todos los demás con pesos no negativos. Voraz (Greedy) con relajación de aristas.
| Vértice | Distancia Tentativa | Previo | Cerrado |
|---|
Nodo fuente A con distancia 0. Los demás a infinito (∞).
Algoritmo de Floyd-Warshall: Todos contra Todos
Calcula caminos mínimos entre todos los pares en O(V³). Evalúa progresivamente si pasar por el nodo intermedio k acorta la distancia entre i y j.
D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]) | D^(k) | A | B | C |
|---|