数据结构重读 – 最小生成树(Prim和Kruskal)

假设要在n个城市之间建立通信网络,则连通n个城市只需要n-1条线路。现在想节省光缆,使得路径和最小。

这一问题就是最小代价生成树问题(Minimum Cost Spanning Tree),简称MST。

MST性质:假设N=(V, {E})是一个连通图,U是顶点集合V的一个非空子集,若(u, v)是一条具有最小权值的边,u属于U且v属于V-U。则必存在一棵包含边(u, v)的最小生成树。

因此,可以采用贪心算法解决。

1、Prim(普里姆)算法

我们需要设置两个辅助数组cost和ivex,它们需要联合在一起使用。

i表示一个尚未被选择的顶点的下标(尚属于V-U)。cost[i]为U中所有顶点中到i的最小权值,ivex[i]即为U中的这个顶点。

因此初始情况下,我们使得ivex[*] = v0, cost[i] = arcs[v0][i]。

每次,选择cost最小的一个的i,然后ivex[i]就是新选择边的起始点,i就是终结点。

代码如下:

测试图如下:

测试数据:

上面实线的这个Prim算法的时间复杂读是O(n^2),主要耗费在选取min cost上。而这一过程,可以用堆(优先队列)实现,使得复杂度降低为O((V+E)*logV)。

由此,Prim算法适用于稠密图中求最小生成树

2、Kruskal(克鲁斯卡尔)算法

Kruskal适用于稀疏图中求最小生成树

时间复杂度是O(E log E) 或者 O(E log V)

Kruskal算法的流程非常简单明了,但需要借助两个数据结构:

(1) 堆(优先队列),按照每条Arc的weight,每次取出最小的weight的Arc。
(2) 并查集,用于判断两个顶点vex i和vex j是否属于同一个结合,并可做合并操作。

算法流程:

  • create a forest F (a set of trees), where each vertex in the graph is a separate tree
  • create a set S containing all the edges in the graph
  • while S is nonemptyand F is not yet spanning
    • remove an edge with minimum weight from S
    • if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
    • otherwise discard that edge.

由于实在不喜欢STL的优先队列,用Java实现吧。

首先是并查集,一定不要实现错哦!

然后是Kruskal算法,input是输入参数,kruskal是算法正常执行。

输出结果:

 

 

 

 

 

 

Leave a Reply

Your email address will not be published.