🚀 16 — Graph Algorithms
← Volver a Algoritmos sobre Estructuras
↑ Volver a inicio / Back to home
🎯 Objetivo / Objective
| Español | English |
|---|---|
Implementar los algoritmos clásicos de grafos (BFS, DFS, Dijkstra, Prim, Kruskal, orden topológico y componentes conexas) sobre grafos representados con listas de adyacencia construidas sobre secuencias indexables (ver 04_Numbers.md), usando las representaciones de grafos aprendidas en data_structures_advanced y valores centinela para los casos “no alcanzable”. |
Implement classic graph algorithms (BFS, DFS, Dijkstra, Prim, Kruskal, topological sort, and connected components) over graphs represented with adjacency lists built over indexable sequences (see 04_Numbers.md), using graph representations learned in data_structures_advanced and sentinel values for “unreachable” cases. |
📝 Especificación / Specification
📋 Enunciado / Problem Statement
| Español | English |
Crear un proyecto graph_algorithms con un módulo graph que represente grafos con listas de adyacencia construidas desde secuencias indexables, cuya representación es libre y se declara en el README, y que implemente los algoritmos listados abajo. Los nodos no alcanzables devuelven el valor centinela -1. Sin excepciones. |
Create a graph_algorithms project with a graph module representing graphs with adjacency lists built from indexable sequences, whose representation is free and is declared in the README, and implementing the algorithms below. Unreachable nodes return the sentinel value -1. No exceptions. |
Implementaciones esperadas
| Algoritmo | Estructura clave | Descripción |
|---|---|---|
bfs(graph, start) |
queue | Recorrido en anchura; devuelve distancias desde start (-1 si no alcanzable) |
dfs(graph, start) |
stack (o recursión) | Recorrido en profundidad; devuelve orden de visita |
dijkstra(graph, start) |
priority queue (heap) | Caminos mínimos en grafos con pesos no negativos |
prim(graph) |
priority queue (heap) | Árbol de expansión mínimo (MST) |
kruskal(graph) |
union-find (secuencias indexables) | MST por aristas ordenadas |
topological_sort(graph) |
stack / indegree | Orden topológico de un DAG (-1 si hay ciclo) |
connected_components(graph) |
queue / stack | Número de componentes conexas |
ES: La cola de prioridad se implementa reutilizando el heap de
efficient_sort(Fase 1). La representación del grafo es una lista de adyacencia:adjacency_list[u] = [(v, weight), ...], construida desde secuencias indexables de aristas; su representación concreta es libre y se declara en el README. EN: The priority queue reuses the heap fromefficient_sort(Phase 1). The graph representation is an adjacency list:adjacency_list[u] = [(v, weight), ...], built from indexable edge sequences; its concrete representation is free and is declared in the README.
ES: La indexación de los algoritmos de esta página es local a este módulo, no una capacidad máxima ni una restricción de etiquetas del ADT de
data_structures_advanced. Al adaptar sus vértices explícitos se declara la correspondencia etiqueta ↔ índice, incluidos los vértices aislados; no se confunden cantidad de vértices, cantidad de aristas y presupuesto físico de memoria.EN: Algorithm indexing on this page is local to this module, not a maximum capacity or label restriction on the Advanced ADT. When adapting its explicit vertices, declare the label ↔ index mapping, including isolated vertices; distinguish vertex count, edge count and physical memory budget.
Pseudocódigo / Pseudocode
container graph
.- bfs(adjacency_list, start)
distance = sequence(size(adjacency_list), -1) # sentinela
distance[start] = 0
queue.enqueue(start)
while queue is not empty
u = queue.dequeue()
for (v, _) in adjacency_list[u]
if distance[v] == -1
distance[v] = distance[u] + 1
queue.enqueue(v)
return distance
.- dfs(adjacency_list, start)
visited = sequence(size(adjacency_list), false)
order = []
stack.push(start)
while stack is not empty
u = stack.pop()
if not visited[u]
visited[u] = true
order.append(u)
for (v, _) in adjacency_list[u]
if not visited[v]
stack.push(v)
return order
.- dijkstra(adjacency_list, start)
distance = sequence(size(adjacency_list), INF)
distance[start] = 0
pq = priority_queue()
pq.push((0, start))
while pq is not empty
(dist_u, u) = pq.pop()
if dist_u > distance[u]
continue
for (v, weight) in adjacency_list[u]
new_dist = dist_u + weight
if new_dist < distance[v]
distance[v] = new_dist
pq.push((new_dist, v))
return distance # INF -> -1 al retornar
.- prim(adjacency_list)
... # MST: crecer el árbol con la arista mínima
.- kruskal(edges, n)
... # ordenar aristas por peso + union-find
.- topological_sort(adjacency_list)
... # Kahn (indegree) o DFS; -1 si detecta ciclo
.- connected_components(adjacency_list)
... # contar componentes con BFS/DFS
end container
Casos de prueba / Test Cases
| Algoritmo | Entrada | Salida esperada |
|---|---|---|
bfs |
grafo de 5 nodos, aristas (0,1),(0,2),(1,3), start=0 |
[0,1,1,2,-1] |
dfs |
mismo grafo, start=0 | visita todos los alcanzables, 4 nodos |
dijkstra |
pesos: (0,1,4),(0,2,1),(2,1,2),(1,3,1), start=0 |
[0,3,1,4] |
prim |
grafo completo de 4 nodos con pesos dados | peso total 7 |
kruskal |
mismas aristas | peso total 7 |
topological_sort |
DAG 5→2, 5→0, 4→0, 4→1, 2→3 | orden válido con 5 antes de 2 y 3 después de 2 |
topological_sort |
grafo con ciclo 0→1→0 | -1 (sentinela de ciclo) |
connected_components |
dos componentes: {0,1,2}, {3,4} | 2 |
✅ Criterios de aceptación / Acceptance Criteria
- ES: Todos los algoritmos se implementan con estructuras construidas sobre secuencias indexables propias (sin colecciones externas). EN: All algorithms use structures built over own indexable sequences (no external collections).
- ES: Los casos “no alcanzable”/”ciclo” devuelven
-1(valores centinela, sin excepciones).
EN: “Unreachable”/”cycle” cases return-1(sentinel values, no exceptions). - ES: Dijkstra usa la cola de prioridad basada en el heap de Fase 1.
EN: Dijkstra uses the priority queue based on the Phase 1 heap. - ES: El proyecto separa
src/detest/y usa el framework de pruebas del lenguaje.
EN: The project separatessrc/fromtest/and uses the language’s test framework.
📂 Ubicación esperada / Expected Location
programming_languages/
└── {language}/
└── core/
└── structures/
└── graph_algorithms/
├── src/
│ └── graph.ext # Módulo de grafos
└── test/
├── graph_test.ext # Suite de pruebas
└── run_tests.ext # Punto de entrada
▶️ Siguiente / Next
👉 Sigue con 17_Backtracking.md — Recursión con retroceso (N-Queens, permutaciones, laberinto).
👉 Continue with 17_Backtracking.md — Backtracking recursion (N-Queens, permutations, maze).