Kruskal 算法

1def find(parent, x):2    while parent[x] != x:3        parent[x] = parent[parent[x]]  # path compression4        x = parent[x]5    return x6
7
8def kruskal(vertices, edges):9    # Take the cheapest edge that does not close a cycle10    parent = {v: v for v in vertices}11    mst, total = [], 012    for w, u, v in sorted(edges):13        root_u, root_v = find(parent, u), find(parent, v)14        if root_u != root_v:15            parent[root_u] = root_v16            mst.append((u, v, w))17            total += w18    return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23    (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24    (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29    print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)

1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3    ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4    ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8    // Union-find with path compression detects cycles cheaply9    const parent = Object.fromEntries(nodes.map((n) => [n, n]));10    const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11    const mst = [];12    let total = 0;13    const sorted = [...edges].sort((a, b) => a[2] - b[2]);14    for (const [u, v, w] of sorted) {15        const rootU = find(u);16        const rootV = find(v);17        if (rootU !== rootV) {18            parent[rootU] = rootV;19            mst.push(`${u}-${v} (${w})`);20            total += w;21        }22    }23    return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);

1import java.util.Arrays;2
3public class Main {4    static int[] parent;5
6    static int find(int x) {7        if (parent[x] != x) parent[x] = find(parent[x]); // path compression8        return parent[x];9    }10
11    static boolean union(int a, int b) {12        int rootA = find(a), rootB = find(b);13        if (rootA == rootB) return false; // would create a cycle14        parent[rootA] = rootB;15        return true;16    }17
18    public static void main(String[] args) {19        int n = 6;20        int[][] edges = {21            {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22            {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23        };24        Arrays.sort(edges, (a, b) -> a[2] - b[2]);25        parent = new int[n];26        for (int i = 0; i < n; i++) parent[i] = i;27
28        int total = 0, used = 0;29        for (int[] e : edges) {30            if (union(e[0], e[1])) {31                System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32                total += e[2];33                if (++used == n - 1) break;34            }35        }36        System.out.println("MST total weight: " + total);37    }38}

1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7    int u, v, weight;8};9
10struct DSU {11    std::vector<int> parent;12    explicit DSU(int n) : parent(n) {13        std::iota(parent.begin(), parent.end(), 0);14    }15    int find(int x) {16        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression17        return parent[x];18    }19    bool unite(int a, int b) {20        int ra = find(a), rb = find(b);21        if (ra == rb) return false;  // would create a cycle22        parent[ra] = rb;23        return true;24    }25};26
27int main() {28    const int n = 5;29    std::vector<Edge> edges = {30        {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31        {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32    };33    // Greedily take the cheapest edge that connects two components34    std::sort(edges.begin(), edges.end(),35              [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36    DSU dsu(n);37    int total = 0;38    std::cout << "MST edges:\n";39    for (const Edge& e : edges) {40        if (dsu.unite(e.u, e.v)) {41            std::cout << "  " << e.u << " - " << e.v42                      << " (weight " << e.weight << ")\n";43            total += e.weight;44        }45    }46    std::cout << "Total weight: " << total << "\n";47    return 0;48}

1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8    int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14    if (parent[x] != x) parent[x] = find(parent[x]);  // path compression15    return parent[x];16}17
18bool unite(int a, int b) {19    int ra = find(a), rb = find(b);20    if (ra == rb) return false;  // would create a cycle21    parent[ra] = rb;22    return true;23}24
25int cmpEdge(const void* a, const void* b) {26    return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30    Edge edges[] = {31        {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32        {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33    };34    int m = sizeof(edges) / sizeof(edges[0]);35    for (int i = 0; i < N; i++) parent[i] = i;36    // Greedily take the cheapest edge that connects two components37    qsort(edges, m, sizeof(Edge), cmpEdge);38    int total = 0;39    printf("MST edges:\n");40    for (int i = 0; i < m; i++) {41        if (unite(edges[i].u, edges[i].v)) {42            printf("  %d - %d (weight %d)\n",43                   edges[i].u, edges[i].v, edges[i].weight);44            total += edges[i].weight;45        }46    }47    printf("Total weight: %d\n", total);48    return 0;49}