最小生成树算法

发布时间：2022-04-11编辑：windydeng浏览（2606）评论览（0）

• Kruskal算法

文字表述:

1. 新建图G，G中拥有原图中相同的节点，但没有边

2. 将原图中所有的边按权值从小到大排序

3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中

4. 重复3，直至图G中所有的节点都在同一个连通分量中

Input: A connected undirected graph G = (V;E) with edge weights w_e

Output: A minimum spanning tree defined by the edges X

for all u ∈ V:

make set(u)

X = {}

Sort the edges E byweight

//每次选取权重最小的边作为操作对象

for all edges {u,v}∈ E, in increasing order of weight:

　　//如果边的两个端点在不同的集合中，那么我们可以将该边加进来,

　　//使集合两个连通组件相互连通

　　if find(u) ≠find(v):

　　add edge {u,v} toX

　　union(u,v)

　　//如果两个端点已经在同一个连通图中，那么加进该边就会形成环

　　//因此舍弃该边

　　if find(u) =find(v): do nothing

 

 

辅助函数：

makeset(x):构建一个只包含节点x的集合

find(x):找出节点所属的集合

union(x;y): 合并分别包含元素x和y的两个集合

 

通过辅助函数，我们就可以确定各个节点是否已经组合在了一个连通图，当所有的节点都在一个连通图中时，我们就得到了最小生成树。

在DPV一书中，给出了这些辅助函数的一种实现方式，同时还对union函数进行了优化，不过这一部分不是最小生成树算法的主体了，更多的是在研究数据结构方面对算法的贡献。

• Prim算法

该算法的思想是从已经形成树的部分出发，一步步向外扩张，找到离已形成连通图的部分“最近”的点将其加进来。

文字表述：

从单一顶点开始，prime算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；

2. 初始化：V_new= {x}，其中x为集合V中的任一节点（起始点），E_new= {}；

3. 重复下列操作，直到V_new= V：

1. 在集合E中选取权值最小的边（u,v），其中u为集合V_new中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

2. 将v加入集合V_new中，将（u,v）加入集合E_new中；

4. 输出：使用集合V_new和E_new来描述所得到的最小生成树。

 

procedure prim(G,w)

Input: A connected undirected graph G = (V;E) with edge weights w_e

Output: A minimum spanning tree defined by the array prev

for all u ∈ V :

　　cost(u)= ∞

　　prev(u)= nil

Pickany initial node u₀

　　cost(u₀)= 0

H = makequeue(V) (priority queue, using cost-values as keys)

while H is not empty:

　　v = deletemin(H)

　　foreach (v; z) ∈ E:

　　　　if cost(z) > w(v; z):

　　　　　　cost(z)= w(v; z) //<*>

　　　　　　prev(z)= v

　　　　　　decreasekey(H;z)

 

对比求最短路径的Dijkstra算法，我们会发现他们有极高的相似度

 

procedure dijkstra(G;l; s)

Input: Graph G = (V;E), directed or undirected; positive edge lengths {le : e∈E};vertex s ∈ V

Output:For all vertices u reachable from s, dist(u) is set to the distance from s to u.

for all u∈V :

　　dist(u)= 1

　　prev(u)= nil

dist(s)= 0

H = makequeue(V) (using dist-values as keys)

while|H|>0 :

　　u = deletemin(H)

　　for all edges (u; v) ∈ E:

　　if dist(v) > dist(u) + l(u; v):

　　　　dist(v)= dist(u) + l(u; v) //<*>

　　　　prev(v)= u

　　　　decreasekey(H;v)

 

除了<*>的部分，Prim是直接将边的权重赋上，Dijkstra则是加上前序的累积权重。所以理解和算法记忆上（其实理解了也不用可以去记忆算法的具体实现了，不过对于初学的我还是需要对这些主要的算法做强化记忆），在懂了Dijkstra之后看Prim就不会有很大的难度。