O BFS da parte 7 estava correto porque toda aresta custava o mesmo. Dê pesos às arestas e ele deixa de estar correto — um caminho com mais saltos agora pode ser mais barato, e o BFS se compromete com a primeira chegada.
Todo programa abaixo está completo, foi rodado no .NET 10, e a saída dele está colada da execução.
Padrão 36 — Dijkstra
Sempre expanda o nó mais barato ainda não fixado, e não o mais próximo em saltos. Depois que um nó é expandido assim, a distância dele é definitiva, porque qualquer outra rota até ele teria que passar por algo que já é mais caro.
PriorityQueue<TElement, TPriority> faz o trabalho. O que ele não tem é DecreaseKey — não há como entrar no heap e baixar a prioridade de um nó. Então o C# usa a abordagem preguiçosa: quando uma distância melhora, insira o nó de novo, e descarte a cópia desatualizada quando ela finalmente aparecer.
O PriorityQueue do C# não tem DecreaseKey, então uma distância melhorada é inserida de novo em vez de atualizada no lugar. O heap acaba guardando as duas, e a obsoleta é descartada quando aparece. O heap cresce para O(E) em vez de O(V), o que quase sempre é a troca certa.
int n = 6;
(int u, int v, int w)[] edges =
[
(0, 1, 10), (0, 2, 1), (2, 1, 1), (1, 3, 2),
(2, 4, 8), (4, 5, 1), (3, 5, 4),
];
List<(int to, int w)>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<(int, int)>())];
foreach (var (u, v, w) in edges) { adj[u].Add((v, w)); adj[v].Add((u, w)); }
int[] dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;
// C# has no DecreaseKey, so stale entries are pushed and skipped on the way out.
PriorityQueue<int, int> pq = new();
pq.Enqueue(0, 0);
while (pq.TryDequeue(out int u, out int d))
{
if (d > dist[u]) { Console.WriteLine($" skip stale entry for {u} (d={d}, best is {dist[u]})"); continue; }
Console.WriteLine($"settle {u} at distance {d}");
foreach (var (v, w) in adj[u])
{
if (dist[u] + w >= dist[v]) continue;
dist[v] = dist[u] + w;
pq.Enqueue(v, dist[v]);
Console.WriteLine($" -> {v} improved to {dist[v]}");
}
}
Console.WriteLine($"\ndistances from 0: [{string.Join(", ", dist)}]");
Console.WriteLine($"\nBFS would call 0->1 one hop and stop there, costing 10.");
Console.WriteLine($"Dijkstra takes 0->2->1, two hops, costing {dist[1]}.");Ele imprime:
settle 0 at distance 0
-> 1 improved to 10
-> 2 improved to 1
settle 2 at distance 1
-> 1 improved to 2
-> 4 improved to 9
settle 1 at distance 2
-> 3 improved to 4
settle 3 at distance 4
-> 5 improved to 8
settle 5 at distance 8
settle 4 at distance 9
skip stale entry for 1 (d=10, best is 2)
distances from 0: [0, 2, 1, 4, 9, 8]
BFS would call 0->1 one hop and stop there, costing 10.
Dijkstra takes 0->2->1, two hops, costing 2.A última linha do trace é o padrão funcionando. O nó 1 foi inserido com distância 10, depois melhorou para 2 e foi inserido de novo. As duas entradas ficaram no heap; a boa saiu primeiro e fixou o nó; a obsoleta apareceu no fim e foi pulada pelo if (d > dist[u]) continue;.
Essa única linha é toda a remoção preguiçosa. Tire ela e os nós são expandidos duas vezes com distâncias erradas.
A saída também mostra por que o BFS não basta aqui. 0 -> 1 é um único salto custando 10; 0 -> 2 -> 1 são dois saltos custando 2. O BFS pegaria o primeiro e nunca reconsideraria.
Custo: O(E log V), com um heap guardando até O(E) entradas em vez de O(V) — o preço de não ter DecreaseKey, e quase sempre vale a pena pagar.
Use quando as arestas têm pesos não negativos. Pesos negativos quebram por completo o argumento de que “fixado é definitivo”, e aí você precisa de Bellman–Ford.
Padrão 37 — BFS 0-1
Agora um caso especial que aparece o tempo todo: toda aresta custa 0 ou 1. Quebrar uma parede custa 1 e andar custa 0; trocar de linha custa 1 e ficar na mesma custa 0.
Dijkstra funciona. E também faz trabalho à toa. O heap existe para achar a menor distância na fronteira, e com só arestas 0 e 1 a fronteira nunca guarda mais que duas distâncias distintas — d e d+1.
Então guarde a fronteira em um deque. Uma aresta 0 produz a mesma distância, então ela vai na frente. Uma aresta 1 produz uma a mais, então vai no fim. O deque fica ordenado sem nenhuma comparação.
O heap do Dijkstra existe para achar a menor distância da fronteira. Quando toda aresta é 0 ou 1, a fronteira só abrange dois valores — então colocar cada nó novo na ponta certa mantém tudo ordenado, e a busca inteira cai de O(E log V) para O(V + E).
// Every edge costs 0 or 1. A heap still works, and is pure overhead: with only
// two possible distances in play, a deque keeps the frontier sorted for free.
int n = 6;
(int u, int v, int w)[] edges =
[
(0, 1, 0), (1, 2, 1), (0, 2, 1), (2, 3, 0), (3, 4, 1), (1, 4, 1), (4, 5, 0),
];
List<(int to, int w)>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<(int, int)>())];
foreach (var (u, v, w) in edges) { adj[u].Add((v, w)); adj[v].Add((u, w)); }
int[] dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;
LinkedList<int> dq = [];
dq.AddFirst(0);
while (dq.Count > 0)
{
int u = dq.First!.Value;
dq.RemoveFirst();
Console.WriteLine($"take {u} (distance {dist[u]})");
foreach (var (v, w) in adj[u])
{
if (dist[u] + w >= dist[v]) continue;
dist[v] = dist[u] + w;
// Weight 0 keeps the same distance, so it belongs at the FRONT.
// Weight 1 is one further out, so it belongs at the BACK.
if (w == 0) { dq.AddFirst(v); Console.WriteLine($" -> {v} = {dist[v]} (0-edge, push FRONT)"); }
else { dq.AddLast(v); Console.WriteLine($" -> {v} = {dist[v]} (1-edge, push BACK)"); }
}
}
Console.WriteLine($"\ndistances: [{string.Join(", ", dist)}]");Ele imprime:
take 0 (distance 0)
-> 1 = 0 (0-edge, push FRONT)
-> 2 = 1 (1-edge, push BACK)
take 1 (distance 0)
-> 4 = 1 (1-edge, push BACK)
take 2 (distance 1)
-> 3 = 1 (0-edge, push FRONT)
take 3 (distance 1)
take 4 (distance 1)
-> 5 = 1 (0-edge, push FRONT)
take 5 (distance 1)
distances: [0, 0, 1, 1, 1, 1]O log V some. Em um grid grande isso é uma diferença real, e o código é mais curto que o Dijkstra que ele substitui.
É também por isso que a parte 5 se deu ao trabalho de usar um ring buffer. O LinkedList<int> é usado acima por clareza e aloca um nó por inserção.
Custo: O(V + E).
Use quando todo peso de aresta é 0 ou 1. Reconhecer isso é toda a habilidade — o problema vai descrever isso em palavras, não em números.
Padrão 38 — Union-Find
Uma pergunta diferente: não quão distantes dois nós estão, mas apenas se eles estão conectados — com as conexões chegando uma de cada vez.
Cada conjunto é uma árvore, e cada nó aponta para o pai. Dois nós estão no mesmo conjunto quando chegam à mesma raiz. Duas otimizações deixam isso quase de graça, e você quer as duas.
União por tamanho pendura a árvore menor embaixo da maior, então a profundidade cresce devagar. Compressão de caminho reaponta cada nó por onde passa direto para a raiz, então fazer uma pergunta barateia a próxima.
Cada operação é O(α(n)) — a função inversa de Ackermann, que fica abaixo de 5 para qualquer entrada que caiba na memória. Trate como constante, mas mantenha as duas otimizações: qualquer uma sozinha é bem pior.
int n = 8;
int[] parent = [.. Enumerable.Range(0, n)];
int[] size = [.. Enumerable.Repeat(1, n)];
// Path HALVING: iterative, so it cannot overflow the stack, and it flattens
// the tree as it walks.
int Find(int x)
{
while (parent[x] != x)
{
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool Union(int a, int b)
{
int ra = Find(a), rb = Find(b);
if (ra == rb) return false; // already together
if (size[ra] < size[rb]) (ra, rb) = (rb, ra); // hang the smaller tree off the bigger
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
foreach (var (a, b) in new[] { (0, 1), (2, 3), (1, 2), (4, 5), (6, 7), (5, 6) })
{
bool merged = Union(a, b);
Console.WriteLine($"union({a},{b}) {(merged ? "merged " : "no-op ")} parent = [{string.Join(",", parent)}]");
}
// Snapshot BEFORE any Find runs — a Find is what does the flattening, so
// asking a question first would hide the effect.
Console.WriteLine($"\nafter the unions : parent = [{string.Join(",", parent)}]");
Console.WriteLine($" node 3 points at 2, which points at 0. Two hops to the root.");
for (int i = 0; i < n; i++) Find(i);
Console.WriteLine($"after Find on all: parent = [{string.Join(",", parent)}] <- flattened");
Console.WriteLine($" every node now points straight at its root. One hop.");
Console.WriteLine($"\nunion(0,3) -> {Union(0, 3)} (already in the same set)");
Console.WriteLine($"connected(0,3): {Find(0) == Find(3)}");
Console.WriteLine($"connected(0,7): {Find(0) == Find(7)}");
Console.WriteLine($"components: {Enumerable.Range(0, n).Select(Find).Distinct().Count()}");Ele imprime:
union(0,1) merged parent = [0,0,2,3,4,5,6,7]
union(2,3) merged parent = [0,0,2,2,4,5,6,7]
union(1,2) merged parent = [0,0,0,2,4,5,6,7]
union(4,5) merged parent = [0,0,0,2,4,4,6,7]
union(6,7) merged parent = [0,0,0,2,4,4,6,6]
union(5,6) merged parent = [0,0,0,2,4,4,4,6]
after the unions : parent = [0,0,0,2,4,4,4,6]
node 3 points at 2, which points at 0. Two hops to the root.
after Find on all: parent = [0,0,0,0,4,4,4,4] <- flattened
every node now points straight at its root. One hop.
union(0,3) -> False (already in the same set)
connected(0,3): True
connected(0,7): False
components: 2As duas linhas de parent no meio são o ponto. Depois das uniões, o nó 3 aponta para 2 que aponta para 0 — dois saltos. Depois de um Find por nó, tudo aponta direto para a raiz.
O Find aqui usa path halving: parent[x] = parent[parent[x]] a cada passo. Ele é iterativo, então não pode estourar a pilha do jeito que a versão recursiva estoura em uma árvore degenerada, e achata quase tão bem.
Vale a pena manter o Union retornando um bool. false significa que os dois já estavam conectados — que é exatamente o teste de ciclo de que o próximo padrão precisa.
Custo: O(α(n)) amortizado por operação. Essa é a função inversa de Ackermann, e ela fica abaixo de 5 para qualquer n que caiba na memória. Constante, na prática.
Use quando as conexões chegam aos poucos e você precisa de conectividade, contagem de componentes ou detecção de ciclo. Ele não consegue separar um conjunto de volta — se você precisa disso, o problema é outro.
Padrão 39 — Árvore geradora mínima de Kruskal
Conecte tudo o mais barato possível.
Ordene as arestas por peso e pegue cada uma, a não ser que as pontas dela já estejam conectadas. É só isso — a escolha gulosa está correta, e o union-find é o que deixa o teste de conectividade rápido.
int n = 6;
(int u, int v, int w)[] edges =
[
(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2),
(2, 3, 4), (3, 4, 2), (4, 5, 6), (3, 5, 3),
];
int[] parent = [.. Enumerable.Range(0, n)];
int[] size = [.. Enumerable.Repeat(1, n)];
int Find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
bool Union(int a, int b)
{
int ra = Find(a), rb = Find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
parent[rb] = ra; size[ra] += size[rb];
return true;
}
int total = 0;
List<(int, int, int)> chosen = [];
foreach (var e in edges.OrderBy(e => e.w))
{
bool took = Union(e.u, e.v);
Console.WriteLine($"edge {e.u}-{e.v} weight {e.w} {(took ? "TAKE " : "skip ")} {(took ? "" : "both ends already connected — it would close a cycle")}");
if (!took) continue;
chosen.Add((e.u, e.v, e.w));
total += e.w;
}
Console.WriteLine($"\nedges chosen: {chosen.Count} (a tree on {n} nodes always has {n - 1})");
Console.WriteLine($"total weight: {total}");Ele imprime:
edge 1-2 weight 1 TAKE
edge 1-3 weight 2 TAKE
edge 3-4 weight 2 TAKE
edge 0-2 weight 3 TAKE
edge 3-5 weight 3 TAKE
edge 0-1 weight 4 skip both ends already connected — it would close a cycle
edge 2-3 weight 4 skip both ends already connected — it would close a cycle
edge 4-5 weight 6 skip both ends already connected — it would close a cycle
edges chosen: 5 (a tree on 6 nodes always has 5)
total weight: 11O Union retornando false é a checagem de ciclo. Sem percurso à parte, sem array de visitados. As três arestas puladas na saída são, cada uma, uma que teria fechado um ciclo.
A contagem final é uma checagem de sanidade de graça: uma árvore geradora sobre n nós tem exatamente n-1 arestas. Menos que isso significa que o grafo estava desconectado, e isso normalmente vale reportar em vez de ignorar.
Custo: O(E log E) para a ordenação, e na prática O(E) para o union-find.
Use quando você precisa de uma árvore geradora mínima, ou de conectar todos os pontos com custo mínimo. O algoritmo de Prim é a alternativa e é melhor em grafos densos; o Kruskal é mais fácil de acertar.
Padrão 40 — Ciclos em um grafo dirigido
A parte 7 detectava ciclos dirigidos com um contador — se a ordenação topológica emitisse menos de n nós, havia um ciclo. Isso diz que existe um ciclo. Não diz onde.
Três cores dizem. Branco é intocado, cinza está no caminho em que você está pisando agora, preto é terminado.
Encontrar um nó cinza significa uma aresta de volta para o caminho debaixo dos seus pés, que é um ciclo. Encontrar um nó preto significa um nó que você já terminou de explorar — perfeitamente normal, e não é um ciclo. Juntar esses dois casos em uma única flag “visitado” é o bug clássico, e ele reporta ciclos em grafos acíclicos.
// Three colours. WHITE untouched, GREY on the current path, BLACK finished.
// Meeting a GREY node means an edge back into the path you are standing on,
// which is a cycle. Meeting BLACK is just a node you already finished.
const int White = 0, Grey = 1, Black = 2;
static List<int>? FindCycle(int n, (int u, int v)[] edges)
{
List<int>[] outs = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) outs[u].Add(v);
int[] colour = new int[n];
int[] parent = new int[n];
Array.Fill(parent, -1);
List<int>? cycle = null;
bool Dfs(int u)
{
colour[u] = Grey;
foreach (int v in outs[u])
{
if (colour[v] == Grey)
{
cycle = [v];
for (int at = u; at != v; at = parent[at]) cycle.Add(at);
cycle.Add(v);
cycle.Reverse();
return true;
}
if (colour[v] == White) { parent[v] = u; if (Dfs(v)) return true; }
}
colour[u] = Black;
return false;
}
for (int i = 0; i < n; i++)
if (colour[i] == White && Dfs(i)) return cycle;
return null;
}
(int, int)[] acyclic = [(0, 1), (0, 2), (1, 3), (2, 3)];
Console.WriteLine($"0->1, 0->2, 1->3, 2->3");
Console.WriteLine($" node 3 is reached twice, but the second time it is BLACK, not GREY.");
Console.WriteLine($" cycle: {(FindCycle(4, acyclic) is null ? "none" : "found")}");
(int, int)[] cyclic = [(0, 1), (1, 2), (2, 3), (3, 1)];
var found = FindCycle(4, cyclic);
Console.WriteLine($"\n0->1, 1->2, 2->3, 3->1");
Console.WriteLine($" cycle: {string.Join(" -> ", found!)}");Ele imprime:
0->1, 0->2, 1->3, 2->3
node 3 is reached twice, but the second time it is BLACK, not GREY.
cycle: none
0->1, 1->2, 2->3, 3->1
cycle: 1 -> 2 -> 3 -> 1No primeiro grafo o nó 3 é alcançável tanto por 1 quanto por 2. Uma única flag visited veria o 3 duas vezes e chamaria isso de ciclo. Três cores veem que o 3 é preto — terminado, não no caminho atual — e corretamente não reportam nada.
Como o parent é registrado na descida, o ciclo em si pode ser reconstruído voltando a partir do nó cinza.
Para um grafo não dirigido nada disso é necessário: rode o union-find do padrão 38, e uma aresta cujas pontas já estão conectadas é um ciclo.
Custo: O(V + E).
Use quando você precisa do ciclo em si, e não só da existência dele — relatórios de deadlock, erros de dependência que têm que nomear o ciclo.
O que lembrar
-
Pesos quebram o BFS. Mais saltos podem ser mais baratos. Se os custos das arestas diferem em qualquer medida, o BFS está errado, não só mais lento.
-
O
PriorityQueuedo C# não temDecreaseKey. Insira a distância melhorada como uma segunda entrada e pule as obsoletas comif (d > dist[u]) continue;. -
Todas as arestas 0 ou 1 significa nenhum heap. Insira arestas 0 na frente e arestas 1 no fim, e o deque fica ordenado de graça.
-
O union-find precisa das duas otimizações. A união por tamanho mantém as árvores rasas, a compressão de caminho achata o que sobra. Qualquer uma sozinha é bem pior.
-
O path halving é iterativo. Sem recursão, então sem stack overflow em uma árvore degenerada.
-
O
Unionretornandofalseé o teste de ciclo. O Kruskal não precisa de mais nada, e a detecção de ciclo em grafo não dirigido também não. -
Três cores, não uma flag de visitado. Cinza significa no caminho atual; preto significa terminado. Juntar as duas reporta ciclos que não existem.
A parte 9 é programação dinâmica — cinco formatos, e a direção do laço que silenciosamente transforma um deles em um problema diferente.