Dijkstra, BFS 0-1 y Union-Find en C#

El BFS de la parte 7 era correcto porque todas las aristas costaban lo mismo. Dale pesos a las aristas y deja de serlo: un camino con más saltos ahora puede ser más barato, y el BFS se queda con la primera llegada.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la ejecución.

Patrón 36 — Dijkstra

Expande siempre el nodo más barato sin fijar, no el más cercano en saltos. Una vez que un nodo se expande así, su distancia es definitiva, porque cualquier otra ruta hacia él tendría que pasar por algo que ya es más caro.

PriorityQueue<TElement, TPriority> hace el trabajo. Lo que no tiene es DecreaseKey: no hay forma de meter la mano en el heap y bajarle la prioridad a un nodo. Así que C# usa el enfoque perezoso: cuando una distancia mejora, inserta el nodo otra vez, y descarta la copia vieja cuando por fin sale.

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

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.

La última línea del trazo es el patrón funcionando. El nodo 1 se insertó a distancia 10, luego mejoró a 2 y se insertó de nuevo. Las dos entradas quedaron en el heap; la buena salió primero y fijó el nodo; la obsoleta salió al final y if (d > dist[u]) continue; la saltó.

Esa única línea es toda la eliminación perezosa. Quítala y los nodos se expanden dos veces con distancias equivocadas.

La salida también muestra por qué el BFS no basta aquí. 0 -> 1 es un solo salto que cuesta 10; 0 -> 2 -> 1 son dos saltos que cuestan 2. El BFS tomaría el primero y nunca lo reconsideraría.

Costo: O(E log V), con un heap que guarda hasta O(E) entradas en vez de O(V): el precio de no tener DecreaseKey, y casi siempre vale la pena pagarlo.

Úsalo cuando las aristas tienen pesos no negativos. Los pesos negativos rompen por completo el argumento de “lo fijado es definitivo”, y ahí necesitas Bellman–Ford.

Patrón 37 — BFS 0-1

Ahora un caso especial que aparece todo el tiempo: cada arista cuesta 0 o 1. Romper un muro cuesta 1 y caminar cuesta 0; cambiar de línea cuesta 1 y quedarte en una cuesta 0.

Dijkstra funciona. También hace trabajo de más. El heap existe para hallar la menor distancia de la frontera, y con aristas de solo 0 y 1 la frontera nunca tiene más de dos distancias distintas: d y d+1.

Así que guarda la frontera en un deque. Una arista 0 produce la misma distancia, así que va al frente. Una arista 1 produce una más, así que va al final. El deque queda ordenado sin una sola comparación.

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

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]

log V desaparece. En una cuadrícula grande eso es una diferencia real, y el código es más corto que el Dijkstra que reemplaza.

Esta es también la razón por la que la parte 5 se molestó con un búfer circular. Arriba se usa LinkedList<int> por claridad, y asigna un nodo por inserción.

Costo: O(V + E).

Úsalo cuando cada peso de arista es 0 o 1. Reconocer eso es toda la habilidad: el problema lo va a describir con palabras, no con números.

Patrón 38 — Union-Find

Otra pregunta distinta: no qué tan lejos están dos nodos, sino apenas si están conectados o no, con las conexiones llegando de a una.

Cada conjunto es un árbol, y cada nodo apunta a su padre. Dos nodos están en el mismo conjunto cuando llegan a la misma raíz. Dos optimizaciones hacen esto casi gratis, y quieres las dos.

La unión por tamaño cuelga el árbol más chico debajo del más grande, así la profundidad crece despacio. La compresión de caminos reapunta cada nodo por el que pasa directo a la raíz, así que hacer una pregunta abarata la siguiente.

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

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: 2

Las dos líneas de parent del medio son el punto. Después de las uniones, el nodo 3 apunta a 2 que apunta a 0: dos saltos. Después de un Find por nodo, todo apunta directo a su raíz.

Aquí Find usa path halving: parent[x] = parent[parent[x]] en cada paso. Es iterativo, así que no puede desbordar la pila como sí puede la versión recursiva en un árbol degenerado, y aplana casi igual de bien.

Que Union devuelva un bool vale la pena conservarlo. false significa que los dos ya estaban conectados, que es exactamente la prueba de ciclo que necesita el patrón siguiente.

Costo: O(α(n)) amortizado por operación. Esa es la función inversa de Ackermann, y es menor que 5 para cualquier n que quepa en memoria. Constante, en la práctica.

Úsalo cuando las conexiones llegan de a poco y necesitas conectividad, conteo de componentes o detección de ciclos. No puede volver a separar un conjunto: si necesitas eso, estás en otro problema.

Patrón 39 — El árbol de expansión mínima de Kruskal

Conecta todo lo más barato posible.

Ordena las aristas por peso y toma cada una salvo que sus extremos ya estén conectados. Eso es todo: la elección voraz es correcta, y union-find es lo que hace rápida la prueba de conectividad.

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

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: 11

Que Union devuelva false es la prueba de ciclo. Sin recorrido aparte, sin arreglo de visitados. Cada una de las tres aristas saltadas en la salida habría cerrado un ciclo.

El conteo final es una verificación gratis: un árbol de expansión sobre n nodos tiene exactamente n-1 aristas. Menos significa que el grafo estaba desconectado, y eso casi siempre conviene reportarlo en vez de ignorarlo.

Costo: O(E log E) por el ordenamiento, y en la práctica O(E) por el union-find.

Úsalo cuando necesitas un árbol de expansión mínima, o conectar todos los puntos al mínimo costo. El algoritmo de Prim es la alternativa y es mejor en grafos densos; Kruskal es más fácil de hacer bien.

Patrón 40 — Ciclos en un grafo dirigido

La parte 7 detectaba ciclos dirigidos con un contador: si el orden topológico emitía menos de n nodos, había un ciclo. Eso te dice que existe un ciclo. No te dice dónde.

Tres colores sí. Blanco es intacto, gris es que está en el camino sobre el que estás parado ahora, negro es terminado.

Encontrar un nodo gris significa una arista de vuelta al camino bajo tus pies, y eso es un ciclo. Encontrar un nodo negro significa un nodo que ya terminaste de explorar: perfectamente normal, y no es un ciclo. Juntar esos dos casos en una sola bandera de “visitado” es el error clásico, y reporta ciclos en 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!)}");

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 -> 1

En el primer grafo el nodo 3 es alcanzable desde 1 y desde 2. Una sola bandera visited vería 3 dos veces y lo llamaría ciclo. Tres colores ve que 3 es negro (terminado, no en el camino actual) y correctamente no reporta nada.

Como parent se registra en la bajada, el ciclo en sí se puede reconstruir caminando hacia atrás desde el nodo gris.

Para un grafo no dirigido nada de esto hace falta: corre el union-find del patrón 38, y una arista cuyos extremos ya están conectados es un ciclo.

Costo: O(V + E).

Úsalo cuando necesitas el ciclo mismo y no solo su existencia: reportes de bloqueo mutuo, errores de dependencias que tienen que nombrar el ciclo.

Qué recordar

• Los pesos rompen el BFS. Más saltos pueden ser más baratos. Si los costos de las aristas difieren aunque sea un poco, el BFS está mal, no solo es más lento.

• El PriorityQueue de C# no tiene DecreaseKey. Inserta la distancia mejorada como segunda entrada y salta las obsoletas con if (d > dist[u]) continue;.

• Todas las aristas 0 o 1 significa ningún heap. Manda las aristas 0 al frente y las aristas 1 al final, y el deque queda ordenado gratis.

• Union-find necesita las dos optimizaciones. La unión por tamaño mantiene los árboles bajos, la compresión de caminos aplana lo que queda. Cualquiera sola es bastante peor.

• Path halving es iterativo. Sin recursión, así que no hay desbordamiento de pila en un árbol degenerado.

• Que Union devuelva false es la prueba de ciclo. Kruskal no necesita nada más, y la detección de ciclos no dirigidos tampoco.

• Tres colores, no una bandera de visitado. Gris significa en el camino actual; negro significa terminado. Juntarlos reporta ciclos que no existen.

La parte 9 es programación dinámica: cinco formas, y la dirección del bucle que en silencio convierte una de ellas en un problema distinto.