本文共 1760 字,大约阅读时间需要 5 分钟。
关于图的几个概念定义:
下面介绍两种求最小生成树算法
对于最小生成树问题,有两种解决方法,*Prim*与*Kruskacl*,复杂度分别为O(m*logn) O(m*logm),一下是对其两种算法的简单介绍
Kruskal算法
Kruskal(克鲁斯卡尔)算法是一种巧妙利用并查集来求最小生成树的算法。
首先我们把无向图中相互连通的一些点称为处于同一个连通块中。例如下图
图中有3个连通块。1、2处于一个连通块中,4、5、6也处于一个连通块中,孤立点3也称为一个连通块。
Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。
算法描述:
if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序,所以必为最小),
①合并u,v所在的集合,相当于把边(u,v)加入最小生成树。
②tot=tot+W(u,v)
③k++
④如果k=n-1,说明最小生成树已经生成,则break;
此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序; 2. 把图中的n个顶点看成独立的n棵树组成的森林; 3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。
由于不断向集合u中加点,所以最小代价边必须同步更新;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息,:
Prim算法
Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想:白点代表已经进入最小生成树的点,蓝点代表未进入最小生成树的点。
算法描述:
以1为起点生成最小生成树,min[v]表示蓝点v与白点相连的最小边权。MST表示最小生成树的权值之和。
一:初始化:min[v]= ∞(v≠1); min[1]=0;MST=0;
二:for (i = 1; i<= n; i++)
1.寻找min[u]最小的蓝点u。
2.将u标记为白点
3.MST+=min[u]
4.for 与白点u相连的所有蓝点v
if (w[u][v]<min[v])
min[v]=w[u][v];