最小生成树Prim与Kruskal

算法图最小生成树

算法

发布日期: 2024-09-25

作者: 小乐

文章字数: 548

阅读时长: 2 分

阅读次数:

一、最小生成树(MST)

1.1 定义

连通无向图中，连接所有顶点的边权和最小的树。

1.2 性质

包含 ( V ) 个顶点和 ( V-1 ) 条边
无环
可能不唯一

1.3 切割定理

任取一个切割， crossing edge（横切边）中权值最小的边一定属于某棵MST。

二、Prim算法

2.1 核心思想

从某个顶点开始，逐步扩展树，每次添加连接树与非树顶点的最小权边。

2.2 实现（优先队列）

public int prim(List<int[]>[] adj) {
    int n = adj.length;
    boolean[] inMST = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{0, 0});  // {vertex, weight}
    int totalWeight = 0;
    int edges = 0;
    
    while (!pq.isEmpty() && edges < n) {
        int[] curr = pq.poll();
        int u = curr[0], w = curr[1];
        
        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += w;
        edges++;
        
        for (int[] edge : adj[u]) {
            int v = edge[0], weight = edge[1];
            if (!inMST[v]) {
                pq.offer(new int[]{v, weight});
            }
        }
    }
    return totalWeight;
}

2.3 复杂度

( O(E \log V) )

三、Kruskal算法

3.1 核心思想

按边权从小到大排序，依次选择不形成环的边，直到选出 ( V-1 ) 条。

3.2 并查集

class UnionFind {
    int[] parent;
    
    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }
}

3.3 实现

public int kruskal(int[][] edges, int n) {
    // edges: [u, v, weight]
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int totalWeight = 0;
    int edgesUsed = 0;
    
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            totalWeight += edge[2];
            if (++edgesUsed == n - 1) break;
        }
    }
    return totalWeight;
}