Recorrido de grafos en C#: BFS, DFS y orden topológico

Los problemas de grafos en C# tienen una forma específica de fallar, y ocurre antes de que corra cualquier algoritmo. Está en cómo se guardó el grafo.

Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de esa ejecución.

Patrón 31 — Cómo se guarda el grafo

List<List<int>> es lo que usan casi todas las soluciones en C#. Se lee bien y es correcto. También asigna un objeto List por nodo, cada uno con su propio arreglo interno, dispersos por el heap. Con 200,000 nodos eso son 200,000 objetos que asignar, y cada consulta de vecinos es un salto de puntero a otro lugar de la memoria.

La alternativa es compressed sparse row: todo el grafo en dos arreglos planos.

int n = 5;
(int u, int v)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)];

// The version most C# solutions use: n List objects, each with its own array.
List<List<int>> adj = [];
for (int i = 0; i < n; i++) adj.Add([]);
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

Console.WriteLine("List<List<int>>:");
for (int i = 0; i < n; i++) Console.WriteLine($"  {i}: [{string.Join(", ", adj[i])}]");
Console.WriteLine($"  objects allocated: 1 outer list + {n} inner lists + their backing arrays");

// Compressed sparse row: two arrays, total, for the whole graph.
int[] head = new int[n + 1];
foreach (var (u, v) in edges) { head[u + 1]++; head[v + 1]++; }   // degree, offset by one
for (int i = 0; i < n; i++) head[i + 1] += head[i];               // prefix sum -> start offsets

int[] next = new int[edges.Length * 2];
int[] cursor = (int[])head.Clone();
foreach (var (u, v) in edges)
{
    next[cursor[u]++] = v;
    next[cursor[v]++] = u;
}

Console.WriteLine($"\nCSR:");
Console.WriteLine($"  head = [{string.Join(", ", head)}]");
Console.WriteLine($"  next = [{string.Join(", ", next)}]");
Console.WriteLine($"  objects allocated: 2 arrays, whatever the size of the graph");

Console.WriteLine("\nneighbours of each node, read from CSR:");
for (int u = 0; u < n; u++)
{
    var nb = new List<int>();
    for (int e = head[u]; e < head[u + 1]; e++) nb.Add(next[e]);
    Console.WriteLine($"  {u}: [{string.Join(", ", nb)}]   (same: {nb.OrderBy(x => x).SequenceEqual(adj[u].OrderBy(x => x))})");
}

Imprime:

List<List<int>>:
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2, 4]
  4: [3]
  objects allocated: 1 outer list + 5 inner lists + their backing arrays

CSR:
  head = [0, 2, 4, 6, 9, 10]
  next = [1, 2, 0, 3, 0, 3, 1, 2, 4, 3]
  objects allocated: 2 arrays, whatever the size of the graph

neighbours of each node, read from CSR:
  0: [1, 2]   (same: True)
  1: [0, 3]   (same: True)
  2: [0, 3]   (same: True)
  3: [1, 2, 4]   (same: True)
  4: [3]   (same: True)

Mira cómo se construye head. Cuentas el grado de cada nodo en head[u+1] y luego tomas una suma de prefijos — el mismo truco de la parte 3, usado aquí para convertir grados en desplazamientos de inicio. cursor es una copia que se va consumiendo mientras llenas, así que el tramo de cada nodo se escribe en orden.

Los vecinos de u son next[head[u] .. head[u+1] - 1]. head tiene n+1 celdas, así que head[u+1] siempre existe para el último nodo — la misma disciplina de desfase por uno que en el arreglo de sumas de prefijos.

¿Vale la pena? No para un grafo de 5 nodos, y no cuando alguien más tiene que leer el código. Vale la pena cuando n está en los cientos de miles, y ahí es la diferencia entre una solución que pasa y una que no.

Úsalo cuando el grafo es grande y estático. Si vas agregando aristas sobre la marcha, quédate con las listas.

Patrón 32 — BFS para caminos más cortos

En un grafo sin pesos, la búsqueda en anchura da caminos más cortos, y lo hace sin comparar nunca dos distancias.

La razón es la cola. Contiene una capa entera antes de contener algo de la siguiente, así que la primera vez que se llega a un nodo, se llega por un camino más corto. Nunca hay uno más corto que encontrar después.

int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];

List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

int start = 0, goal = 5;

int[] dist = new int[n];
int[] parent = new int[n];
Array.Fill(dist, -1);
Array.Fill(parent, -1);

Queue<int> q = [];
q.Enqueue(start);
dist[start] = 0;

while (q.Count > 0)
{
    int u = q.Dequeue();
    Console.WriteLine($"visit {u} (distance {dist[u]})");
    foreach (int v in adj[u])
    {
        if (dist[v] != -1) continue;          // already has its shortest distance
        dist[v] = dist[u] + 1;
        parent[v] = u;
        q.Enqueue(v);
        Console.WriteLine($"      -> {v} first reached, distance {dist[v]}");
    }
}

List<int> path = [];
for (int at = goal; at != -1; at = parent[at]) path.Add(at);
path.Reverse();

Console.WriteLine($"\ndistances: [{string.Join(", ", dist)}]");
Console.WriteLine($"path {start} -> {goal}: {string.Join(" -> ", path)}  (length {dist[goal]})");

Imprime:

visit 0 (distance 0)
      -> 1 first reached, distance 1
      -> 2 first reached, distance 1
visit 1 (distance 1)
      -> 3 first reached, distance 2
visit 2 (distance 1)
      -> 6 first reached, distance 2
visit 3 (distance 2)
      -> 4 first reached, distance 3
visit 6 (distance 2)
visit 4 (distance 3)
      -> 5 first reached, distance 4
visit 5 (distance 4)

distances: [0, 1, 1, 2, 3, 4, 2]
path 0 -> 5: 0 -> 1 -> 3 -> 4 -> 5  (length 4)

La línea crítica es if (dist[v] != -1) continue; junto con fijar dist[v] en el momento de encolar, no de desencolar. Si marcas al desencolar, varios vecinos pueden meter el mismo nodo antes de que se procese, aparece varias veces en la cola y la infla hasta O(aristas).

parent cuesta un arreglo y te da la ruta real, no solo su longitud. Camina hacia atrás desde la meta y voltea el resultado. Casi todos los problemas que piden una distancia terminan pidiendo el camino.

Costo: O(V + E) en tiempo y espacio.

Úsalo cuando las aristas no tienen peso, o todas tienen el mismo peso. Si difieren, esto da respuestas incorrectas y lo que quieres es la parte 8.

Patrón 33 — DFS sin la pila de llamadas

El DFS recursivo es más corto y se lee mejor. También corre en un hilo cuya pila mide, por defecto, 1MB — y un camino de 100,000 nodos la agota.

Esto importa más en C# que en otros lenguajes, porque una StackOverflowException no se puede atrapar. El runtime termina el proceso. No hay manejador de excepciones, no hay mensaje de error sobre el que puedas actuar, solo un proceso muerto y un veredicto.

Dos soluciones. Conviértelo a una pila explícita, o dale a la recursión una pila propia más grande.

using System.Threading;

int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];
List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

// Explicit stack. Same traversal, no call frames.
bool[] seen = new bool[n];
Stack<int> st = [];
List<int> order = [];

st.Push(0);
while (st.Count > 0)
{
    int u = st.Pop();
    if (seen[u]) continue;        // a node can be pushed several times before it is popped
    seen[u] = true;
    order.Add(u);

    // Pushed in reverse so the smallest neighbour is popped first.
    for (int i = adj[u].Count - 1; i >= 0; i--)
        if (!seen[adj[u][i]]) st.Push(adj[u][i]);
}
Console.WriteLine($"iterative DFS order: {string.Join(" -> ", order)}");

// How deep can recursion go? On the default 1MB main-thread stack, not very.
// A StackOverflowException cannot be caught in .NET — the process just dies —
// so the fix is to give the recursion its own thread with a bigger stack.
int depth = 0;
void Deep(int k) { if (k == 0) return; depth++; Deep(k - 1); }

var t = new Thread(() => Deep(500_000), 256 * 1024 * 1024);
t.Start();
t.Join();
Console.WriteLine($"recursion on a 256MB stack: reached depth {depth:N0}, no crash");

Imprime:

iterative DFS order: 0 -> 1 -> 3 -> 2 -> 6 -> 4 -> 5
recursion on a 256MB stack: reached depth 500,000, no crash

La versión explícita tiene una sutileza: if (seen[u]) continue; después de sacar el nodo. Varios vecinos pueden meter un nodo antes de que se saque, así que el mismo índice aparece legítimamente en la pila más de una vez y hay que saltarlo en las visitas posteriores. Meter los vecinos en orden inverso hace que el recorrido coincida con el que habría hecho la versión recursiva.

El truco del hilo es la otra vía, y es lo que hace mucho código de concurso en C#. new Thread(action, 256 * 1024 * 1024) le da a la recursión un cuarto de gigabyte de pila, y la salida de arriba muestra medio millón de marcos sin ningún problema. Conserva el código recursivo, que para DP en árboles es una ventaja real.

Úsalo cuando el grafo es profundo — un grafo camino, un árbol degenerado, una cuadrícula recorrida a lo largo. Si la profundidad puede pasar de unas decenas de miles, no lo dejes recursivo en el hilo principal.

Patrón 34 — Flood fill

Componentes conexas en una cuadrícula. Cuenta las islas.

string[] grid =
[
    "11000",
    "11000",
    "00100",
    "00011",
];

int rows = grid.Length, cols = grid[0].Length;
bool[,] seen = new bool[rows, cols];
int islands = 0;

int[] dr = [-1, 1, 0, 0];
int[] dc = [0, 0, -1, 1];

for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
{
    if (grid[r][c] != '1' || seen[r, c]) continue;

    islands++;
    List<(int, int)> cells = [];
    Queue<(int r, int c)> q = [];
    q.Enqueue((r, c));
    seen[r, c] = true;

    while (q.Count > 0)
    {
        var (cr, cc) = q.Dequeue();
        cells.Add((cr, cc));
        for (int d = 0; d < 4; d++)
        {
            int nr = cr + dr[d], nc = cc + dc[d];
            // One bounds check, and mark on ENQUEUE not on dequeue.
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] != '1' || seen[nr, nc]) continue;
            seen[nr, nc] = true;
            q.Enqueue((nr, nc));
        }
    }
    Console.WriteLine($"island {islands}: {cells.Count} cells  {string.Join(" ", cells.Select(x => $"({x.Item1},{x.Item2})"))}");
}

Console.WriteLine($"\nislands: {islands}");

Imprime:

island 1: 4 cells  (0,0) (1,0) (0,1) (1,1)
island 2: 1 cells  (2,2)
island 3: 2 cells  (3,3) (3,4)

islands: 3

La cuadrícula es un grafo; la única diferencia es que los vecinos se calculan en vez de guardarse. Los arreglos dr/dc reducen eso a un solo bucle en vez de cuatro bloques copiados, y agregar diagonales es agregar cuatro entradas en vez de cuatro bloques más.

Vale la pena conservar dos hábitos. Los límites se revisan antes de leer la cuadrícula, en la misma guarda, porque C# evalúa || de izquierda a derecha y es el orden lo que evita que el índice se salga de rango. Y seen se marca al encolar, exactamente por la razón del patrón 32.

Aquí se usa BFS y no DFS justamente porque una mancha grande de celdas es exactamente el caso de recursión profunda del patrón 33. Una cuadrícula de 500×500 llena de unos es una sola componente de 250,000 celdas de profundidad.

Costo: O(filas × columnas).

Úsalo cuando el problema es una cuadrícula — islas, regiones, relleno de pintura, algo que se propaga con el tiempo.

Patrón 35 — Orden topológico, y la detección de ciclos gratis

Ordena los nodos para que toda arista apunte hacia adelante. Planificación de tareas, dependencias de compilación, prerrequisitos de cursos.

El algoritmo de Kahn: cuenta cuántas aristas apuntan a cada nodo, empieza por los que nadie apunta, y cada vez que quitas un nodo, decrementa sus destinos.

int n = 6;
// A directed graph: an edge u -> v means u must come before v.
(int u, int v)[] edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)];

static List<int>? TopoSort(int n, (int u, int v)[] edges)
{
    List<int>[] outs = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
    int[] indeg = new int[n];
    foreach (var (u, v) in edges) { outs[u].Add(v); indeg[v]++; }

    // Everything with nothing pointing at it can go first.
    Queue<int> ready = new(Enumerable.Range(0, n).Where(i => indeg[i] == 0));
    List<int> order = [];

    while (ready.Count > 0)
    {
        int u = ready.Dequeue();
        order.Add(u);
        foreach (int v in outs[u])
            if (--indeg[v] == 0) ready.Enqueue(v);
    }

    // Anything left has a cycle behind it: its in-degree never reached zero.
    return order.Count == n ? order : null;
}

Console.WriteLine($"in-degrees start: {string.Join(", ", Enumerable.Range(0, n).Select(i => $"{i}:{edges.Count(e => e.v == i)}"))}");
var order = TopoSort(n, edges);
Console.WriteLine($"order: {(order is null ? "IMPOSSIBLE" : string.Join(" -> ", order))}");

// Every edge must point forwards in the result.
int[] pos = new int[n];
for (int i = 0; i < order!.Count; i++) pos[order[i]] = i;
Console.WriteLine($"every edge points forwards: {edges.All(e => pos[e.u] < pos[e.v])}");

Console.WriteLine();
(int u, int v)[] cyclic = [(0, 1), (1, 2), (2, 0)];
Console.WriteLine($"with a cycle 0->1->2->0: {(TopoSort(3, cyclic) is null ? "IMPOSSIBLE — detected" : "sorted?!")}");

Imprime:

in-degrees start: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0
order: 4 -> 5 -> 2 -> 0 -> 3 -> 1
every edge points forwards: True

with a cycle 0->1->2->0: IMPOSSIBLE — detected

La detección de ciclos es la parte que vale la pena notar, porque no es una pasada aparte. Si la cola se vacía antes de emitir los n nodos, a lo que quede le sigue apuntando algo — y como nada fuera del ciclo puede estar apuntándolos a todos, tiene que haber un ciclo. order.Count == n es toda la verificación.

La línea de verificación es un buen hábito para cualquier problema de ordenamiento: construye una tabla de posiciones y comprueba que toda arista apunte hacia adelante. Los órdenes topológicos casi nunca son únicos, así que comparar contra una única respuesta esperada es la prueba equivocada.

Costo: O(V + E).

Úsalo cuando el problema describe dependencias, prerrequisitos o restricciones de orden — y siempre que necesites saber si un grafo dirigido tiene algún ciclo.

Qué recordar

• List<List<int>> asigna un objeto por nodo. Está bien para grafos pequeños; con 10⁵ nodos, CSR son dos arreglos para todo y los vecinos quedan contiguos.

• head se construye con una suma de prefijos sobre los grados, y tiene n+1 celdas para que exista el desplazamiento final del último nodo.

• BFS da caminos más cortos solo por las capas. Nada de comparar distancias, y eso es justo lo que deja de funcionar cuando las aristas tienen pesos.

• Marca los nodos cuando los encolas, nunca cuando los desencolas. Si no, el mismo nodo entra a la cola varias veces.

• Una StackOverflowException no se puede atrapar en .NET. La recursión profunda no lanza una excepción; mata el proceso. Usa una pila explícita, o un hilo con una pila grande.

• Un nodo puede estar legítimamente dos veces en la pila explícita. Revisa seen después de sacarlo, no solo antes de meterlo.

• order.Count == n es la verificación del ciclo. No hace falta nada más, y nada menos alcanza.

La parte 8 agrega pesos, donde BFS deja de ser correcto: Dijkstra con PriorityQueue, el caso 0-1 donde el heap es pura sobrecarga, y union-find.