Percurso de grafos em C#: BFS, DFS e ordenação topológica

Problemas de grafos em C# têm um modo de falha específico, e ele acontece antes de qualquer algoritmo rodar. Está em como o grafo foi guardado.

Todo programa abaixo está completo, foi rodado no .NET 10, e a saída dele está colada da execução.

Padrão 31 — Como o grafo é guardado

List<List<int>> é o que a maioria das soluções em C# usa. Lê bem e está correto. Também aloca um objeto List por nó, cada um com o próprio array interno, espalhados pelo heap. Com 200.000 nós isso são 200.000 objetos para alocar, e cada lookup de vizinho é um salto de ponteiro para outro lugar da memória.

A alternativa é compressed sparse row: o grafo inteiro em dois arrays 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))})");
}

Ele 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)

Olhe como head é construído. Conte o grau de cada nó em head[u+1], depois tire uma soma de prefixos — o mesmo truque da parte 3, usado aqui para transformar graus em deslocamentos iniciais. cursor é uma cópia que vai sendo consumida durante o preenchimento, então o trecho de cada nó é escrito em ordem.

Os vizinhos de u são next[head[u] .. head[u+1] - 1]. head tem n+1 células, então head[u+1] sempre existe para o último nó — a mesma disciplina de erro de um do array de soma de prefixos.

Vale a pena? Não para um grafo de 5 nós, e não quando o código tem que ser lido por outra pessoa. Vale a pena quando n está na casa das centenas de milhares, e é a diferença entre uma solução que passa e uma que não passa.

Use quando o grafo for grande e estático. Se você vai adicionando arestas conforme avança, fique com as listas.

Padrão 32 — BFS para caminhos mínimos

Num grafo sem pesos, a busca em largura dá caminhos mínimos, e faz isso sem nunca comparar duas distâncias.

O motivo é a fila. Ela guarda uma camada inteira antes de guardar qualquer coisa da próxima, então na primeira vez que um nó é alcançado, ele é alcançado por um caminho mínimo. Nunca existe um mais curto para achar depois.

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]})");

Ele 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)

A linha crítica é if (dist[v] != -1) continue; combinada com definir dist[v] no momento da entrada na fila, não da saída. Marque na saída e um nó pode ser empurrado por vários vizinhos antes de ser processado, aparecer várias vezes na fila, e inflar a fila para O(arestas).

parent custa um array e dá a rota de verdade, não só o comprimento dela. Volte a partir do destino e inverta. A maioria dos problemas que pede uma distância acaba pedindo o caminho.

Custo: O(V + E) de tempo e espaço.

Use quando as arestas não tiverem peso, ou todas tiverem o mesmo peso. Se elas diferem, isto dá respostas erradas e você quer a parte 8.

Padrão 33 — DFS sem a pilha de chamadas

O DFS recursivo é mais curto e lê melhor. Ele também roda numa thread cuja pilha tem, por padrão, 1MB — e um caminho de 100.000 nós esgota isso.

Isso importa mais em C# do que em algumas outras linguagens, porque uma StackOverflowException não pode ser capturada. O runtime encerra o processo. Não há handler de exceção, não há mensagem de erro sobre a qual agir, só um processo morto e um veredito.

Duas saídas. Converter para uma pilha explícita, ou dar à recursão uma pilha maior só dela.

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");

Ele imprime:

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

A versão explícita tem uma sutileza: if (seen[u]) continue; depois do pop. Um nó pode ser empurrado por vários vizinhos antes de ser desempilhado, então o mesmo índice aparece legitimamente na pilha mais de uma vez e precisa ser pulado nas visitas seguintes. Empurrar os vizinhos em ordem inversa faz o percurso bater com o que a versão recursiva teria feito.

O truque da thread é o outro caminho, e é o que muito código C# de maratona faz. new Thread(action, 256 * 1024 * 1024) dá à recursão um quarto de gigabyte de pilha, e a saída acima mostra meio milhão de frames sem nenhum problema. Ele mantém o código recursivo, o que para DP em árvore é uma vantagem de verdade.

Use quando o grafo for profundo — um grafo caminho, uma árvore degenerada, uma grade percorrida pelo lado longo. Se a profundidade pode passar de algumas dezenas de milhares, não deixe recursivo na thread principal.

Padrão 34 — Flood fill

Componentes conexas numa grade. Conte as ilhas.

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}");

Ele 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

A grade é um grafo; a única diferença é que os vizinhos são calculados em vez de guardados. Os arrays dr/dc mantêm isso em um laço só, em vez de quatro blocos copiados, e adicionar diagonais é adicionar quatro entradas em vez de mais quatro blocos.

Dois hábitos valem a pena. Os limites são checados antes de a grade ser lida, na mesma guarda, porque C# avalia || da esquerda para a direita e é a ordem que impede o índice de sair da faixa. E seen é marcado na entrada da fila, exatamente pelo motivo do padrão 32.

O BFS é usado aqui em vez do DFS justamente porque uma mancha grande de células é exatamente o caso de recursão profunda do padrão 33. Uma grade 500×500 só de uns é uma única componente com 250.000 células de profundidade.

Custo: O(linhas × colunas).

Use quando o problema for uma grade — ilhas, regiões, preenchimento de tinta, algo se espalhando com o tempo.

Padrão 35 — Ordenação topológica, e a checagem de ciclo de graça

Ordene os nós para que toda aresta aponte para frente. Agendamento de tarefas, dependências de build, pré-requisitos de cursos.

O algoritmo de Kahn: conte quantas arestas apontam para cada nó, comece pelos que ninguém aponta, e cada vez que você remove um nó, decremente os alvos dele.

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?!")}");

Ele 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

A detecção de ciclo é a parte que vale notar, porque não é uma passada separada. Se a fila esvazia antes de todos os n nós saírem, o que sobrou ainda tem algo apontando para ele — e como nada fora do ciclo pode estar apontando para todos eles, tem que haver um ciclo. order.Count == n é a checagem inteira.

A linha de verificação é um bom hábito para qualquer problema de ordenação: monte um lookup de posições e confira que toda aresta aponta para frente. Ordenações topológicas normalmente não são únicas, então comparar com uma única resposta esperada é o teste errado.

Custo: O(V + E).

Use quando o problema descrever dependências, pré-requisitos, ou restrições de ordem — e sempre que você precisar saber se um grafo dirigido tem algum ciclo.

O que lembrar

• List<List<int>> aloca um objeto por nó. Tudo bem para grafos pequenos; com 10⁵ nós, o CSR são dois arrays para tudo e os vizinhos ficam contíguos.

• head é construído com uma soma de prefixos sobre os graus, e tem n+1 células para que o deslocamento final do último nó exista.

• BFS só dá caminho mínimo por causa das camadas. Nenhuma comparação de distância, e é exatamente isso que para de funcionar quando as arestas têm peso.

• Marque os nós quando você os coloca na fila, nunca quando você os tira. Senão o mesmo nó entra na fila várias vezes.

• Uma StackOverflowException não pode ser capturada no .NET. Recursão profunda não lança nada; ela mata o processo. Use uma pilha explícita, ou uma thread com uma pilha grande.

• Um nó pode legitimamente estar duas vezes na pilha explícita. Cheque seen depois de desempilhar, não só antes de empilhar.

• order.Count == n é a checagem de ciclo. Nada mais é preciso, e nada menos serve.

A parte 8 adiciona pesos, onde o BFS deixa de estar correto: Dijkstra com PriorityQueue, o caso 0-1 onde o heap é puro overhead, e union-find.