Kruskal和Prim算法的分析研究与比较

贺军忠，王丽君

(陇南师范高等专科学校 电子商务学院，甘肃 成县 742500)

关于最小生成树问题有两种经典的算法，克鲁斯克尔(Kruskal)算法和普里姆(Prim)算法。在程序设计中，最小生成树问题出现的次数并不是很多，所以直接使用这些算法的机会也不多。不过，Kruskal算法是互斥集合数据结构的优秀应用示例[1]，相同结构的算法常常得到广泛应用，值得研究。而Prim算法与迪杰斯特拉算法类似，几乎与迪杰斯特拉算法具有完全相同的形态，也常常被使用。虽然Kruskal算法和Prim算法都使用贪心法，工作原理相同，从没有任何边线的状态开始向树结构逐条添加边线。但两种算法的运行机制大不相同，执行方式存在很大差异。

1 Kruskal算法分析

1.1 Kruskal算法概述

通常是加权值最小的边线包含于最小生成树。Kruskal的最小生成树算法也是基于这种原理设计而成的[2]。该算法会按照升序排列图结构中的所有边线，然后把各条边线逐条添加到生成树。当然，并不能因为加权值小就把边线无条件添加到生成树，这样做有可能产生回路。因此，需要先考虑那些会产生回路的边线并排除。Kruskal算法会按照这种方式检查所有边线，之后终止算法[3]。

1.2 Kruskal算法执行过程分析

图1表示Kruskal算法对图结构找出最小生成树的执行过程。图1中用粗实线表示添加到最小生成树的边线，a～f表示顶点，1～5表示两顶点间的加权值。刚开始先选择两条最短的边线(a，c)和(b，d)，然后按顺序选择了加权值为2和3的边线。需要说明的是从图(d)到图(e)的过程，此过程中，虽然还有两条加权值为3的边线，但是添加了权值为4的(c，d)。因为若添加了加权值为3的边线，就会形成回路而破坏树结构。最终得到的图(f)中，边线连接了图结构的所有顶点，而且没有产生任何回路。

1.3 Kruskal算法的时间复杂度分析

通过分析算法的执行过程就能了解Kruskal算法的实现方法与时间复杂度。首先得到边线目录并按照加权值大小排序，然后遍历这些边线并添加到生成树。此时最重要的部分是，添加新边线后，判断此边线和已添加的边线是否形成回路。这可以说是Kruskal算法的核心部分。要完成这种高效判断，首先想到的方法是，把边线添加到树结构后，对树结构进行深度优先搜索，确认是否存在逆向边[4]。这种方法会对每条边线都执行1次深度优先搜索，因此，整个算法的时间复杂度是深度优先搜索的时间复杂度O(|V|+|E|)再乘上|E|的结果值，即O(|E|2)。

1.4 Kruskal算法的实现方法分析

代码1-1表示Kruskal算法的实现方法，此代码使用了DisjointSet类。排序边线目录时，把边线添加到pair

代码1-1Kruskal最小生成树算法

structDisjointSet;

constint MAX_V=100;

int V;

vector

intkruskal(vector&selected){

int ret=0;

selected.clear();

vectoredges;

for(int u=0;u

for(inti=0;i

int b=adj[u][i].first,cost=adj[u][i].second;

edges.push_back(make_pair(cost,make_pair(u,v)));

}

sort(edges.begin(),edges.End());

Disjointsetsets(V);

for(inti=0;i

int cost.edges(i).first;

int u=.edges[i].second.first,v.=edges[i].second second;

if(sets.find(u)==sets.find(v))continue;

sets.merge(u,v);

selected.push_back(make_pair(u,v));

ret=+cost;

}

return ret;

}

2 Prim算法

2.1 Prim算法概述

Prim最小生成树算法的工作原理与Kruskal算法相同，但二者的执行方式存在很大差异[5]。Kruskal算法主要把零星生成的树结构碎片合并以生成最小生成树，而Prim算法会从单个起始点构成的树结构开始，向树结构逐条添加边线以生成树，因此，该过程中选择的边线始终保持连接状态。对已经生成的树结构，Prim算法只会考虑其相邻边线。除了这点外，Prim算法与Kruskal算法完全相同。因为Prim算法也会反复执行在可选边线中选择加权值最小的边线的操作。

2.2 Prim算法执行过程分析

图2表示Prim算法在图结构中找出最小生成树的执行过程。图中，包含于生成树的顶点用同心圆表示，而粗实线表示包含的边线，a～f表示顶点，1～5表示两顶点间的加权值。由图可知，每个阶段都会向树结构添加1条边线。图中灰色虚线表示可能在下一阶段添加到树结构的候选边线，这些候选边线会连接1个隶属于树结构的顶点和1个不属于树结构的顶点。图(c)中的边线(a，b)连接了两个属于树结构的顶点，所以此边线不能成为候选边线。Prim算法会找出加权值最小的候选边线，并将其添加到树结构。这种过程会反复进行，直到找出生成树。

图2 Prim算法的执行过程

2.3 Prim算法的时间复杂度分析

整理上述说明就能编写实现Prim算法的代码。此代码会把各顶点是否包含于树结构的信息保存到布尔类型数组added[]，然后在每个阶段遍历所有边线，找出下一条要添加到树结构的边线。虽然这种实现方法比较容易理解，但会耗费很长的运行时间。添加1个顶点会耗费O(|E|)的运算时间，所以这样编写的代码会具有O(|V||E|)的时间复杂度。Kruskal算法的时间复杂度是O(|E|lg|E|)，这样看来，这种时间复杂度的算法几乎没有什么实用性。如果连接到1个顶点的边线超过两条，此时会逐一检查所有边线，因而会浪费宝贵的运算时间。若理解了这个道理，就能对上述算法进行优化[6]。例如，在图2(b)共有两条边线连接着树和顶点b。此时，因存在长度为1的边线(d，b)，所以长度为5的边线(a，b)就没有任何意义了。因此，对不属于树结构的顶点，只保存连接树结构和顶点的最短边线即可。然后遍历各顶点并找出下一个要添加的顶点，就能够在O(|V|)的运算时间内完成操作。

2.4 Prim算法的实现方法分析

Prim算法会生成数组min Weight[]以保存连接树结构和顶点边线的最小权值。每次添加新顶点时，此数组就会遍历连接此顶点的各条边线，并进行更新[7]。通过这种方法就能在O(|V|)的时间内找出需要添加的新顶点，而只需对所有边线检查两次，因为把u和v添加到树结构时，各检查1次边线(u，v)。所以整个时间复杂度将会是O(|V|2+|E|)。代码2-1表示实现这种方法的算法源代码。为了确认各顶点连接到树结构时实际使用的边线，把使用边线的另一个顶点保存到parent[]。

代码2-1普里姆算法的实现方法

costint MAX_V=100;

constint INF=987654321;

// 顶点个数

int V;

// 图结构的邻接表。保存成对(连接的顶点序号，边线加权值)

vector

// 对给出的图结构，把最小生成树中的边线目录保存到selected，并返回加权值之和

int prim(vector

selected.clear();

//相应顶点是否已包含到树结构。

vectorsbool> added(V,false);

// 保存树结构相邻边线中接到相应顶点的最小边线的信息。

vectorminweight(V,INF),parent(V,-1);

//保存加权值之和的变量

Intren=0;

// /以0号顶点为起点：总是最先添加到树结构。

Minweight[0]-parent[0]=0

for(intiter=0;iter

//找出下一个要添加到树结构的顶点u

int u=1;

for(int v=0;v

if(!added[v]&&s(u==-1 ||minweight[u]>minweitght[v]))

u=v;

//把(parent[u],u)加到树结构。

if(parent[u]!=0)

selected.push_back(nake_pair(parent[u],u));

ret+=minweight[u];

added[u]=true;

//检u的相邻边线(u,v)

for(inti=0;i

int v=adj[u][i].first,weight=adj[u[i].second;

if(!added(v)&&minweight[v]>weight){

parent[v]=u;

minweight[v]=weight;

}

}

}

return ret;

}

3 Kruskal和Prim算法比较

Prim算法和Kruskal算法都是最小生成树的经典算法，都可以用贪心法证明两种算法的正确性。根据Kruskal算法的执行过程得知，需要对所有边线按权重从小到大进行排序，在没有形成回路的前提下，依次将边线权重最小的加到最小生成树中。因此，边数较少时可以用Kruskal算法。Kruskal算法在找最小生成树结点之前，将排序好的权重边依次加到最小生成树中，当所有的结点都加到最小生成树中后，就找到了这个连通图的最小生成树[8]。当边数较多时可以用Prim算法，因为它是每次加一个顶点，对边数多的适用。虽然Prim最小生成树算法的工作原理与Kruskal算法相同，但二者的执行方式存在很大差异。Prim算法是从单个起始点构成的树结构开始，向树结构逐条添加边线以生成树。也就是说，Prim最小生成树是从一个具有n个顶点的带权无向完全图中选择n-1条边并使这个图连通，同时使生成树的权值最小。Prim算法从图中的一个顶点开始，把这个顶点包含在一个集合中，反复寻找一个顶点已在该集合中而另一个顶点还不在该集合中的最小权边，把新边和新结点归并到生成树中，找到这个连通图的最小生成树。从方法上来看，Kruskal是需要先对权重边线排序后再查找，一次就能根据权重边线找到最小生成树；而Prim算法是直接查找，多次迭代寻找邻边的权重最小值，所以从时间复杂度上来说，Kruskal在算法效率上比Prim更快[9]。

4 结论

通过对克鲁斯克尔(Kruskal)算法和普里姆(Prim)算法进行分析研究，并从两种算法的执行过程，时间复杂度、实现方法等几个方面进行对比分析，得出了在不同图结构中，两种算法各自的优缺点，为解决实际问题提供相应的理论依据。具体而言，从执行方法上来看，Kruskal是需要先对权重边线排序后再查找，一次就能根据权重边线找到最小生成树；而Prim算法是直接查找，多次迭代寻找邻边的权重最小值，最终找到最小生成树；从时间复杂度上来说，Kruskal在算法效率上比Prim更快。总之，在图结构中边数较少时采用Kruskal算法，边数较多时采用Prim算法较合理。