九.最小生成树

1.Prime算法

Prim 算法（普里姆）：从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

Prim 最小生成树-w:
MST Weight: 0
Start:
准备就绪
Weighted Graph (Prim)
2314526A
B
C
D
E
Prim's Algorithm
void Prim(Graph G, int start) {
    MST = {}; Visited = {start};
    PQ.add(edges from start);
    while (!PQ.empty()) {
        edge(u, v) = PQ.popMin();
        if (v is not in Visited) {
            Visited.add(v);
            MST.add(edge);
            PQ.add(edges from v);
       }
    }
}
Priority Queue & MSTSize: 0
队列为空

如上图所示:

选取P城当作顶点开始构建生成树;
观察与P城相连的代价最小的点,为学校; 将学校纳入生成树中:
观察此时与P城相连的代价最小的顶点为:矿场和渔村;
将矿场纳入生成树中;
此时,学校,P城,矿场构成了一棵生成树;
找与这棵树相连的代价最小的顶点:渔村;
将渔村纳入生成树;且与矿场相连;
此时,P城,矿场,渔村,学校构成了一棵生成树;
观察,与此树相连且代价最小的为:农场;
最后,电站与农村相连代价最小;

2.Kruskal算法

Kruskal 算法（克鲁斯卡尔）：每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）,直到所有结点都连通

Kruskal 最小生成树-w:
MST Weight: 0
准备就绪
Weighted Graph (Kruskal)
2314526A
B
C
D
E
Kruskal's Algorithm
void Kruskal(Graph G) {
    MST = {};
    SortedEdges = Sort(G.edges, by weight);
    DSU.init(G.nodes); // 并查集初始化
    for (edge(u, v) in SortedEdges) {
        if (DSU.find(u) != DSU.find(v)) {
            MST.add(edge);
            DSU.union(u, v);
        }
    }
}
Sorted Edges (Global List)Size: 7
B — C
w=1
A — B
w=2
C — E
w=2
A — C
w=3
B — D
w=4
C — D
w=5
D — E
w=6