图—最小生成树 Prime 和 Kruskal 算法

图的最小生成树的算法,这个问题要解决的问题场景很简单,要给几个地方修建铁路把它们连接起来。

如下图,黑色加粗的边表示是最小生成树的边。
最小生成树

如果最理想的情况,可以假设我们知道任意一点到其他点的距离,也就是边的权重,整个图应该是连通的,那我们开始修路吧
其实这里有一个变形,我们在教科书中讲解的是距离,但是在这里实际上我们可以将其放宽,例如修建成本,开发时间等等其他条件。

要解决这个问题一般有两种方法Prime(以点为主) 和 Kruskal 算法(以边为主)
两种方法的核心思想都是从原图G中不断抽取符合条件的点或边,填充空图 R,最后R中会形成 N个点和N-1条边 ,Prime 在N个点上做文章,Kruskal在N-1条边上做文章。

Prime:
0. 设置一个点 cur 加入到R 中
1. 更新G中与cur相邻且未被访问的点到R的距离,如果发生了更新,记录cur到这些点对应的PRE数组的位置,例如 PRE[i] = cur
2. 选取更新后距离最短的点min,加入到R中,并且增加边 <min, PRE[min]>
3. cur = min ,回到步骤1

这是一种简单的贪心算法,但是因为其符合最优子结构的定义,也就是如果只有子问题达到最优的时候,才能达到全局最优的条件,因此局部最优解也是全局最优解,之后介绍的最短路径中的Kruskal ,Dijkstra也是这样情况,Prime算法强调点,在实现的时候边的主要作用是发挥在更新距离上,有时候如果两点之间存在多条边的情况下(例如两座城市之间,可以同时修多条路,有些是成本不同,有些是时间不同,可进行综合比较),就直接挑选最小的作为更新标准,所以这里面还需要进行一些比较复杂的操作,而人们一般感觉Prime算法简单,是因为它的运行环境自动屏蔽了边方面带来的问题。

接下来介绍Kruskal算法,这个稍微有点别扭,因为这个是直接来操作边的一种最小生成树,直面边的烦恼。它的直观的想法是把挑选N-1个最小边(优先队列),看能不能连接N个点,如果不能(说明形成了环,用并查集),那就把不符合条件的边扔出去,拿下一条最小的。

判断是否成环,是这里的难点,如果少于N个点,形成N-1条边,说明这里肯定有环,这是一个很好的思路,但这是一个充分条件不是必要条件,N个点 N-1条边,同样可能产生环例如 <1,2>,<3,7> ,<2,1> 四个点三条边,有环。

所以我们还需要其他思路,来判断环,我最开始想这个问题时候还曾经犯过一个错误,添加边的时候判断,两个点是否被添加过了,例如<1,2>,<3,7>,<2,3>.

这里判断环的方法是运用并查集,一种能够快速判断,两个元素是否属于同一个集合的方法,典型的应用比如判断两人是否是亲戚。想一下,如果添加边的时候能形成环的话,那么从起点和终点从已经添加的边开始深度遍历,一定能够相遇,这才是成环的充要条件。

那么并查集是否很难呢,其实超简单,总共不超过10行代码。

1. init int parent[]: parent[i] = i;
2. define find:
[sourcecode language=”java”]
int Find(int f, int []parent)
{
return f!=parent[f]?parent[f] = Find(parent[f],parent): parent[f];
}
[/sourcecode]
3 define union:
[sourcecode language=”java”]

boolean union(int s, int f int [] parent)
{
int father = find(f,parent),son = find(f,son);
if(father ==son) return false;
parent[s] = father; return true;
}
[/sourcecode]

Kruskal算法:
1. 初始化,优先队列Q(所有边压入), 并查集Parent, 空图R
2. 弹出队首元素cur
3. 如果cur的首尾元素不在同一集合中 this.Union(parent, e.s, e.e)==true
4. R中添加 e,如果R中的边数达到 N-1 推出循环,否则跳到步骤2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.