Kruskal (árbol de expansión mínima)

class Conjuntos:
    """Conjuntos disjuntos con las dos mejoras: compresión de caminos y unión por tamaño."""

    def __init__(self, elementos):
        self.padre = {x: x for x in elementos}
        self.tam = {x: 1 for x in elementos}

    def raiz(self, x):
        r = x
        while self.padre[r] != r:
            r = self.padre[r]
        while self.padre[x] != r:                   # compresión: el camino apunta ya a la raíz
            sig = self.padre[x]
            self.padre[x] = r
            x = sig
        return r

    def unir(self, x, y):
        rx, ry = self.raiz(x), self.raiz(y)
        if rx == ry:
            return False                            # ya estaban juntos: cerraría un ciclo
        if self.tam[rx] < self.tam[ry]:
            rx, ry = ry, rx
        self.padre[ry] = rx                         # el grupo pequeño cuelga del grande
        self.tam[rx] += self.tam[ry]
        return True


sedes = ["Central", "Norte", "Sur", "Este", "Oeste", "Puerto"]
cables = [
    ("Central", "Norte", 12), ("Central", "Sur", 9), ("Central", "Este", 15),
    ("Central", "Oeste", 10), ("Norte", "Este", 7), ("Norte", "Oeste", 18),
    ("Sur", "Oeste", 11), ("Sur", "Puerto", 6), ("Este", "Puerto", 20),
    ("Oeste", "Puerto", 13), ("Norte", "Sur", 16),
]
cables.sort(key=lambda c: c[2])

grupos = Conjuntos(sedes)
print("Cables de más barato a más caro:")
total = puestos = 0
for a, b, coste in cables:
    if grupos.unir(a, b):
        total += coste
        puestos += 1
        print(f"  sí  {a} - {b} ({coste})")
        if puestos == len(sedes) - 1:
            break                                   # n − 1 cables: ya está todo conectado
    else:
        print(f"  no  {a} - {b} ({coste}): cerraría un ciclo")
print(f"Coste total: {total} con {puestos} cables para {len(sedes)} sedes")

/** Conjuntos disjuntos con las dos mejoras: compresión de caminos y unión por tamaño. */
class Conjuntos {
    constructor(elementos) {
        this.padre = new Map(elementos.map((x) => [x, x]));
        this.tam = new Map(elementos.map((x) => [x, 1]));
    }

    raiz(x) {
        let r = x;
        while (this.padre.get(r) !== r) r = this.padre.get(r);
        while (this.padre.get(x) !== r) {            // compresión: el camino apunta ya a la raíz
            const sig = this.padre.get(x);
            this.padre.set(x, r);
            x = sig;
        }
        return r;
    }

    unir(x, y) {
        let rx = this.raiz(x), ry = this.raiz(y);
        if (rx === ry) return false;                 // ya estaban juntos: cerraría un ciclo
        if (this.tam.get(rx) < this.tam.get(ry)) [rx, ry] = [ry, rx];
        this.padre.set(ry, rx);                      // el grupo pequeño cuelga del grande
        this.tam.set(rx, this.tam.get(rx) + this.tam.get(ry));
        return true;
    }
}

const sedes = ["Central", "Norte", "Sur", "Este", "Oeste", "Puerto"];
const cables = [
    ["Central", "Norte", 12], ["Central", "Sur", 9], ["Central", "Este", 15],
    ["Central", "Oeste", 10], ["Norte", "Este", 7], ["Norte", "Oeste", 18],
    ["Sur", "Oeste", 11], ["Sur", "Puerto", 6], ["Este", "Puerto", 20],
    ["Oeste", "Puerto", 13], ["Norte", "Sur", 16],
];
cables.sort((x, y) => x[2] - y[2]);

const grupos = new Conjuntos(sedes);
console.log("Cables de más barato a más caro:");
let total = 0, puestos = 0;
for (const [a, b, coste] of cables) {
    if (grupos.unir(a, b)) {
        total += coste;
        puestos++;
        console.log(`  sí  ${a} - ${b} (${coste})`);
        if (puestos === sedes.length - 1) break;     // n − 1 cables: ya está todo conectado
    } else {
        console.log(`  no  ${a} - ${b} (${coste}): cerraría un ciclo`);
    }
}
console.log(`Coste total: ${total} con ${puestos} cables para ${sedes.length} sedes`);

using System;
using System.Collections.Generic;
using System.Linq;

record Cable(string A, string B, int Coste);

/// <summary>Conjuntos disjuntos con las dos mejoras: compresión de caminos y unión por tamaño.</summary>
class Conjuntos {
    private readonly Dictionary<string, string> padre = new();
    private readonly Dictionary<string, int> tam = new();

    public Conjuntos(IEnumerable<string> elementos) {
        foreach (string x in elementos) {
            padre[x] = x;
            tam[x] = 1;
        }
    }

    public string Raiz(string x) {
        string r = x;
        while (padre[r] != r) r = padre[r];
        while (padre[x] != r) {                                // compresión: el camino apunta ya a la raíz
            string sig = padre[x];
            padre[x] = r;
            x = sig;
        }
        return r;
    }

    public bool Unir(string x, string y) {
        string rx = Raiz(x), ry = Raiz(y);
        if (rx == ry) return false;                            // ya estaban juntos: cerraría un ciclo
        if (tam[rx] < tam[ry]) (rx, ry) = (ry, rx);
        padre[ry] = rx;                                        // el grupo pequeño cuelga del grande
        tam[rx] += tam[ry];
        return true;
    }
}

class Program {
    static void Main() {
        string[] sedes = { "Central", "Norte", "Sur", "Este", "Oeste", "Puerto" };
        var cables = new List<Cable> {
            new("Central", "Norte", 12), new("Central", "Sur", 9), new("Central", "Este", 15),
            new("Central", "Oeste", 10), new("Norte", "Este", 7), new("Norte", "Oeste", 18),
            new("Sur", "Oeste", 11), new("Sur", "Puerto", 6), new("Este", "Puerto", 20),
            new("Oeste", "Puerto", 13), new("Norte", "Sur", 16),
        }.OrderBy(c => c.Coste).ToList();

        var grupos = new Conjuntos(sedes);
        Console.WriteLine("Cables de más barato a más caro:");
        int total = 0, puestos = 0;
        foreach (var c in cables) {
            if (grupos.Unir(c.A, c.B)) {
                total += c.Coste;
                puestos++;
                Console.WriteLine(
quot;  sí  {c.A} - {c.B} ({c.Coste})");
                if (puestos == sedes.Length - 1) break;        // n − 1 cables: ya está todo conectado
            } else {
                Console.WriteLine(
quot;  no  {c.A} - {c.B} ({c.Coste}): cerraría un ciclo");
            }
        }
        Console.WriteLine(
quot;Coste total: {total} con {puestos} cables para {sedes.Length} sedes");
    }
}

<?php
/** Conjuntos disjuntos con las dos mejoras: compresión de caminos y unión por tamaño. */
class Conjuntos {
    private array $padre = [];
    private array $tam = [];

    public function __construct(array $elementos) {
        foreach ($elementos as $x) {
            $this->padre[$x] = $x;
            $this->tam[$x] = 1;
        }
    }

    public function raiz(string $x): string {
        $r = $x;
        while ($this->padre[$r] !== $r) $r = $this->padre[$r];
        while ($this->padre[$x] !== $r) {          // compresión: el camino apunta ya a la raíz
            $sig = $this->padre[$x];
            $this->padre[$x] = $r;
            $x = $sig;
        }
        return $r;
    }

    public function unir(string $x, string $y): bool {
        $rx = $this->raiz($x);
        $ry = $this->raiz($y);
        if ($rx === $ry) return false;             // ya estaban juntos: cerraría un ciclo
        if ($this->tam[$rx] < $this->tam[$ry]) [$rx, $ry] = [$ry, $rx];
        $this->padre[$ry] = $rx;                   // el grupo pequeño cuelga del grande
        $this->tam[$rx] += $this->tam[$ry];
        return true;
    }
}

$sedes = ["Central", "Norte", "Sur", "Este", "Oeste", "Puerto"];
$cables = [
    ["Central", "Norte", 12], ["Central", "Sur", 9], ["Central", "Este", 15],
    ["Central", "Oeste", 10], ["Norte", "Este", 7], ["Norte", "Oeste", 18],
    ["Sur", "Oeste", 11], ["Sur", "Puerto", 6], ["Este", "Puerto", 20],
    ["Oeste", "Puerto", 13], ["Norte", "Sur", 16],
];
usort($cables, fn($x, $y) => $x[2] <=> $y[2]);

$grupos = new Conjuntos($sedes);
echo "Cables de más barato a más caro:\n";
$total = 0;
$puestos = 0;
foreach ($cables as [$a, $b, $coste]) {
    if ($grupos->unir($a, $b)) {
        $total += $coste;
        $puestos++;
        echo "  sí  $a - $b ($coste)\n";
        if ($puestos === count($sedes) - 1) break; // n − 1 cables: ya está todo conectado
    } else {
        echo "  no  $a - $b ($coste): cerraría un ciclo\n";
    }
}
echo "Coste total: $total con $puestos cables para " . count($sedes) . " sedes\n";

import heapq

cables = [
    ("Central", "Norte", 12), ("Central", "Sur", 9), ("Central", "Este", 15),
    ("Central", "Oeste", 10), ("Norte", "Este", 7), ("Norte", "Oeste", 18),
    ("Sur", "Oeste", 11), ("Sur", "Puerto", 6), ("Este", "Puerto", 20),
    ("Oeste", "Puerto", 13), ("Norte", "Sur", 16),
]
red = {}
for a, b, coste in cables:                          # cada cable, en los dos sentidos
    red.setdefault(a, []).append((coste, a, b))
    red.setdefault(b, []).append((coste, b, a))
dentro = {"Central"}
borde = list(red["Central"])
heapq.heapify(borde)
total = 0
print("Prim desde Central:")
while borde and len(dentro) < len(red):
    coste, a, b = heapq.heappop(borde)              # el cable más barato que sale del árbol
    if b in dentro:
        continue                                    # los dos extremos ya dentro: ciclo
    dentro.add(b)
    total += coste
    print(f"  + {a} - {b} ({coste})")
    for s in red[b]:
        if s[2] not in dentro:
            heapq.heappush(borde, s)
print(f"Coste total: {total}, el mismo que con Kruskal")

const cables = [
    ["Central", "Norte", 12], ["Central", "Sur", 9], ["Central", "Este", 15],
    ["Central", "Oeste", 10], ["Norte", "Este", 7], ["Norte", "Oeste", 18],
    ["Sur", "Oeste", 11], ["Sur", "Puerto", 6], ["Este", "Puerto", 20],
    ["Oeste", "Puerto", 13], ["Norte", "Sur", 16],
];
const red = new Map();
for (const [a, b, coste] of cables) {               // cada cable, en los dos sentidos
    if (!red.has(a)) red.set(a, []);
    if (!red.has(b)) red.set(b, []);
    red.get(a).push([a, b, coste]);
    red.get(b).push([b, a, coste]);
}
const dentro = new Set(["Central"]);
const borde = [...red.get("Central")];              // un array que se ordena hace de cola de prioridad
let total = 0;
console.log("Prim desde Central:");
while (borde.length > 0 && dentro.size < red.size) {
    borde.sort((x, y) => x[2] - y[2]);
    const [a, b, coste] = borde.shift();            // el cable más barato que sale del árbol
    if (dentro.has(b)) continue;                    // los dos extremos ya dentro: ciclo
    dentro.add(b);
    total += coste;
    console.log(`  + ${a} - ${b} (${coste})`);
    for (const s of red.get(b)) if (!dentro.has(s[1])) borde.push(s);
}
console.log(`Coste total: ${total}, el mismo que con Kruskal`);

using System;
using System.Collections.Generic;

record Cable(string A, string B, int Coste);

class Program {
    static void Main() {
        var cables = new List<Cable> {
            new("Central", "Norte", 12), new("Central", "Sur", 9), new("Central", "Este", 15),
            new("Central", "Oeste", 10), new("Norte", "Este", 7), new("Norte", "Oeste", 18),
            new("Sur", "Oeste", 11), new("Sur", "Puerto", 6), new("Este", "Puerto", 20),
            new("Oeste", "Puerto", 13), new("Norte", "Sur", 16),
        };
        var red = new Dictionary<string, List<Cable>>();
        foreach (var c in cables) {                               // cada cable, en los dos sentidos
            if (!red.ContainsKey(c.A)) red[c.A] = new List<Cable>();
            if (!red.ContainsKey(c.B)) red[c.B] = new List<Cable>();
            red[c.A].Add(c);
            red[c.B].Add(new Cable(c.B, c.A, c.Coste));
        }
        var dentro = new HashSet<string> { "Central" };
        var borde = new PriorityQueue<Cable, int>();
        foreach (var c in red["Central"]) borde.Enqueue(c, c.Coste);
        int total = 0;
        Console.WriteLine("Prim desde Central:");
        while (borde.Count > 0 && dentro.Count < red.Count) {
            var c = borde.Dequeue();                              // el cable más barato que sale del árbol
            if (dentro.Contains(c.B)) continue;                   // los dos extremos ya dentro: ciclo
            dentro.Add(c.B);
            total += c.Coste;
            Console.WriteLine(
quot;  + {c.A} - {c.B} ({c.Coste})");
            foreach (var s in red[c.B])
                if (!dentro.Contains(s.B)) borde.Enqueue(s, s.Coste);
        }
        Console.WriteLine(
quot;Coste total: {total}, el mismo que con Kruskal");
    }
}

<?php
$cables = [
    ["Central", "Norte", 12], ["Central", "Sur", 9], ["Central", "Este", 15],
    ["Central", "Oeste", 10], ["Norte", "Este", 7], ["Norte", "Oeste", 18],
    ["Sur", "Oeste", 11], ["Sur", "Puerto", 6], ["Este", "Puerto", 20],
    ["Oeste", "Puerto", 13], ["Norte", "Sur", 16],
];
$red = [];
foreach ($cables as [$a, $b, $coste]) {            // cada cable, en los dos sentidos
    $red[$a][] = [$a, $b, $coste];
    $red[$b][] = [$b, $a, $coste];
}
$dentro = ["Central" => true];
$borde = new SplPriorityQueue();                   // saca la MAYOR prioridad: se usa -coste
foreach ($red["Central"] as $c) $borde->insert($c, -$c[2]);
$total = 0;
echo "Prim desde Central:\n";
while (!$borde->isEmpty() && count($dentro) < count($red)) {
    [$a, $b, $coste] = $borde->extract();          // el cable más barato que sale del árbol
    if (isset($dentro[$b])) continue;              // los dos extremos ya dentro: ciclo
    $dentro[$b] = true;
    $total += $coste;
    echo "  + $a - $b ($coste)\n";
    foreach ($red[$b] as $s)
        if (!isset($dentro[$s[1]])) $borde->insert($s, -$s[2]);
}
echo "Coste total: $total, el mismo que con Kruskal\n";