算法——最小生成树：Kruskal算法、Prim算法

本是古典何须时尚 2022-08-11 18:59 223阅读 0赞

## 最小生成树定义： ##

在一个具有V个节点的连通无向图[![G=(E,V)][G_E_V]][G_E_V_G_E_V]中，找到一个子图[![G^\{\\ast \}][G_ast]][G_ast _G_ast]，该子图包含原图的所有节点和部分连接边，且不能形成回路，同时子图边的权值总和最小。

最小生成树的算法：

根据对安全边的不同规则，有两种算法可以生成最小生成树。即Kruskal算法和Prim算法

## Kruskal算法 ##

Kruskal算法使用的贪婪准则是：从剩下的边中选择一条不会产生环路，且具有最小耗费的边加入已选择的边的集合中；

假设 G=(V,\{E\}) 是一个含有 n 个顶点的连通网，则按照 Kruskal算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

该算法找到安全边的方法是：在所有连接森林中两颗不同树的边里面，找到权值最小的边[![(u,v)][u_v]][u_v_u_v]。

步骤：

1.  在带权值连通图中，按边的权值大小进行排序。
2.  根据权值大小顺序判断集合是否需要该边，若集合需要该边，则将该边的两端节点加入到集合中，并使其连通。
3.  循环第二步，直到所有节点都在集合中。

判断法则：当将边加入到已找到边的集合中时，是否会形成回路？  
 1.如果没有形成回路，那么直接将其连通。此时，对于边的集合又要做一次判断：这两个点是否在已找到点的集合中出现过？  
 ①.如果两个点都没有出现过，那么将这两个点都加入已找到点的集合中；  
 ②.如果其中一个点在集合中出现过，那么将另一个没有出现过的点加入到集合中；  
 ③.如果这两个点都出现过，则不用加入到集合中。  
 2.如果形成回路，不符合要求，直接进行下一次操作。

下面根据带权值连通图对Kruskal算法的工作流程进行讲解：

![SouthEast][]

上图为原图；连接边按照权值的大小排序：即[![\\small hg<(gf=ic)<(cf=ab)<ig<(hi=cd)<(ah=bc)<de<ef<bh<df][small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df]][small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df_small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df]；Kruskal算法按照权值从小到大进行判断，判断连接边节点是否属于集合A。

![SouthEast 1][]

第一步：判断权值为1的连接边hg是否属于集合，由于开始集合为空，则将两个节点加入到集合，且连接该边，并判断是否属于回路；

![SouthEast 2][]

第二步：判断权值为2的连接边ic是否属于集合，由于集合只有节点h和g，则将节点i和c加入到集合中，且连接该边，并判断是否属于回路；

![SouthEast 3][]

第三步：判断权值为2的连接边gf是否属于集合，根据判断规则，把f加入到集合，且连接该边；

![SouthEast 4][]

第四步：根据判断规则，将节点a和b加入到集合，且连接该边；

![SouthEast 5][]

第五步：根据判断规则，连接该边cf；

![SouthEast 6][]

第六步：根据判断规则，连接节点i和g时形成回路，则放弃，继续下次判断；

![SouthEast 7][]

第七步：判断权值为7的连接边；根据判断规则，节点i和h形成回路，则放弃，将节点d加入到集合，并连接该边；

![SouthEast 8][]

第八步：判断权值为8的连接边；根据判断规则，连接节点a和h；

![SouthEast 9][]

第九步：判断权值为9的连接边；将节点e加入到集合，并连接该边；此时集合已经包含所有节点，则终止循环；

算法伪代码：

/** Kruskal算法求解最小生成树 **/
    KRUSKAL-FUNCTION(G, w)
    1    F := 空集合
    2    for each 图 G 中的顶点 v
    3        do 將 v 加入森林 F
    4    对所有的边(u, v) ∈ E依权重 w 进行递增排序
    5    for each 边(u, v) ∈ E
    6        do if u 和 v 不在同一棵子树
    7            then F := F ∪ {(u, v)}
    8                將 u 和 v 所在的子树合并

## Prim算法 ##

Prim 算法过程： 从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点：

1.  输入：一个加权连通图，其中顶点集合为V，边集合为E；
2.  初始化：Vnew = \{x\}，其中x为集合V中的任一节点（起始点），Enew = \{\}；
3.  重复下列操作，直到Vnew = V：
    
     *  在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
     *  将v加入集合Vnew中，将（u, v）加入集合Enew中；
4.  输出：使用集合Vnew和Enew来描述所得到的最小生成树。

该算法所具有的一个性质是集合A中的边总是构成一棵树，而不是森林。这棵树从任意一个根节点开始，一直长大到覆盖V中所有的节点为止。算法每一步在链接集合A和A之外的节点的边，选择一条轻量级边加入到集合A中。

步骤：

设[![G=(E,V)][G_E_V]][G_E_V_G_E_V]是带权值的连通图，A是[![G][]][G 1]上最小生成树中边的集合：  
（1）初始令[![S=\\left \\\{ \\right.u\_\{0\}\\left. \\right \\\}][S_left _ _right.u_0_left. _right]][S_left _ _right.u_0_left. _right _S_left _ _right.u_0_left. _right],([![u\_\{0\}\\epsilon V][u_0_epsilon V]][u_0_epsilon V_u_0_epsilon V]), A=NULL  
（2）在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]  
（3）将[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]并入集合A，同时[![v\_\{0\}][v_0]][v_0_v_0]并入[![S][]][S 1]  
（4）重复上述操作直至[![S=V][S_V]][S_V_S_V]为止，则[![G^\{\\ast \}=(V,A)][G_ast _V_A]][G_ast _V_A_G_ast _V_A]为[![G][]][G 1]的最小生成树

判断规则：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]，连接该边，但不能形成回路；

举例：

![SouthEast 10][]

该图为原始图

第一步：选取一个初始节点a为根节点，并找到权值为最小的边，即为ab；

![SouthEast 11][]

第二步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；即权值最小边为bc或者ah；这里选取bc

![SouthEast 12][]

第三步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；即选择ci；

![SouthEast 13][]

第四步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；即选择cf；

![SouthEast 14][]

第五步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；即选择fg；

![SouthEast 15][]

第六步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；即选择gh；

![SouthEast 16][]

第七步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；必须保证不能形成回路，即选择cd；

![SouthEast 17][]

最后一步：在所有[![u\\epsilon S][u_epsilon S]][u_epsilon S_u_epsilon S],[![v\\epsilon (V-S)][v_epsilon _V-S]][v_epsilon _V-S_v_epsilon _V-S]的边[![(u,v)\\epsilon E][u_v_epsilon E]][u_v_epsilon E_u_v_epsilon E]中，找一条权值最小的边[![(u\_\{0\},v\_\{0\})][u_0_v_0]][u_0_v_0_u_0_v_0]；必须保证不能形成回路，即选择de；由于树包含了所有节点，且满足[![S=V][S_V]][S_V_S_V]，则在此终止，[![G^\{\\ast \}=(V,A)][G_ast _V_A]][G_ast _V_A_G_ast _V_A]为[![G][]][G 1]的最小生成树。

![SouthEast 18][]

[G_E_V]: /images/20220810/e7e70ed65d8c4b4cb2fec6d2668ee85f.png=%28E,V%29
[G_E_V_G_E_V]: http://private.codecogs.com/eqnedit.php?latex=G=%28E,V%29
[G_ast]: /images/20220810/e7e70ed65d8c4b4cb2fec6d2668ee85f.png^%7b\ast&space;%7d
[G_ast _G_ast]: http://private.codecogs.com/eqnedit.php?latex=G^%7b\ast&space;%7d
[u_v]: http://latex.codecogs.com/gif.latex?%28u,v%29
[u_v_u_v]: /images/20220810/b0d90f7ea3c1442fa2fa3a98f40f0dad.png
[SouthEast]: /images/20220810/1fc495f3d5d148fc9637ac190c88f64e.png
[small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df]: http://latex.codecogs.com/gif.latex?\fn_phv&space;\small&space;hg<%28gf=ic%29<%28cf=ab%29<ig<%28hi=cd%29<%28ah=bc%29<de<ef<bh<df
[small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df_small hg_gf_ic_cf_ab_ig_hi_cd_ah_bc_de_ef_bh_df]: http://private.codecogs.com/eqnedit.php?latex=\fn_phv&space;\small&space;hg<%28gf=ic%29<%28cf=ab%29<ig<%28hi=cd%29<%28ah=bc%29<de<ef<bh<df
[SouthEast 1]: /images/20220810/f053f360241a4965adc1996be59c6866.png
[SouthEast 2]: /images/20220810/94edb30070ad4554bc793ff69f72ea71.png
[SouthEast 3]: /images/20220810/91329d1430e04e3aad09fc66bb43cc42.png
[SouthEast 4]: /images/20220810/b006d75dc156492398a6f195b8e2a81a.png
[SouthEast 5]: /images/20220810/c2225a9783174e7c850f9575742b1233.png
[SouthEast 6]: /images/20220810/9be8e64693174c4f97a6f4fe66b4978e.png
[SouthEast 7]: /images/20220810/2fe091e8fed14166a35150a0dea71fb6.png
[SouthEast 8]: /images/20220810/d2aeb127919f4eb5936db0119d428e62.png
[SouthEast 9]: /images/20220810/115925c979ff494fb23c1ad3a714c11e.png
[G]: /images/20220810/e7e70ed65d8c4b4cb2fec6d2668ee85f.png
[G 1]: http://private.codecogs.com/eqnedit.php?latex=G
[S_left _ _right.u_0_left. _right]: /images/20220810/d55e383209674ce48385f27ab9ae8aa8.png=\left&space;\%7b&space;\right.u_%7b0%7d\left.&space;\right&space;\%7d
[S_left _ _right.u_0_left. _right _S_left _ _right.u_0_left. _right]: http://private.codecogs.com/eqnedit.php?latex=S=\left&space;\%7b&space;\right.u_%7b0%7d\left.&space;\right&space;\%7d
[u_0_epsilon V]: http://latex.codecogs.com/gif.latex?u_%7b0%7d\epsilon&space;V
[u_0_epsilon V_u_0_epsilon V]: http://private.codecogs.com/eqnedit.php?latex=u_%7b0%7d\epsilon&space;V
[u_epsilon S]: http://latex.codecogs.com/gif.latex?u\epsilon&space;S
[u_epsilon S_u_epsilon S]: http://private.codecogs.com/eqnedit.php?latex=u\epsilon&space;S
[v_epsilon _V-S]: http://latex.codecogs.com/gif.latex?v\epsilon&space;%28V-S%29
[v_epsilon _V-S_v_epsilon _V-S]: http://private.codecogs.com/eqnedit.php?latex=v\epsilon&space;%28V-S%29
[u_v_epsilon E]: http://latex.codecogs.com/gif.latex?%28u,v%29\epsilon&space;E
[u_v_epsilon E_u_v_epsilon E]: /images/20220810/b0d90f7ea3c1442fa2fa3a98f40f0dad.png\epsilon&space;E
[u_0_v_0]: http://latex.codecogs.com/gif.latex?%28u_%7b0%7d,v_%7b0%7d%29
[u_0_v_0_u_0_v_0]: /images/20220810/6dcc14cea5ab46b882646b8b062f86ef.png
[v_0]: http://latex.codecogs.com/gif.latex?v_%7b0%7d
[v_0_v_0]: http://private.codecogs.com/eqnedit.php?latex=v_%7b0%7d
[S]: /images/20220810/d55e383209674ce48385f27ab9ae8aa8.png
[S 1]: http://private.codecogs.com/eqnedit.php?latex=S
[S_V]: /images/20220810/d55e383209674ce48385f27ab9ae8aa8.png=V
[S_V_S_V]: http://private.codecogs.com/eqnedit.php?latex=S=V
[G_ast _V_A]: /images/20220810/e7e70ed65d8c4b4cb2fec6d2668ee85f.png^%7b\ast&space;%7d=%28V,A%29
[G_ast _V_A_G_ast _V_A]: http://private.codecogs.com/eqnedit.php?latex=G^%7b\ast&space;%7d=%28V,A%29
[SouthEast 10]: /images/20220810/5aa360d1d9e647279ff8fa0f26b08114.png
[SouthEast 11]: /images/20220810/81ff070c77a8486888db4bf85c12fef0.png
[SouthEast 12]: /images/20220810/14129f8d9be04b89b9694bfb6b748f00.png
[SouthEast 13]: /images/20220810/f5bbcb1304ce47a3885764f31f531567.png
[SouthEast 14]: /images/20220810/0a129c5a1c9043b28d605d98fb99374a.png
[SouthEast 15]: /images/20220810/841a8ebb7fb54c8c8fbb5be7c2a50155.png
[SouthEast 16]: /images/20220810/94c18af2d60f475ea8b31938fa51636e.png
[SouthEast 17]: /images/20220810/bad1b29e92b44459a5b536384b5fde64.png
[SouthEast 18]: /images/20220810/c5c07191e19648d2990e398484ed17e5.png