最小生成树的两种经典算法的分析及实现摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。

构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。

关键词：连通图，赋权图，最小生成树，算法，实现1 前言假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。

这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。

n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。

现在要选择这样一棵生成树，也就是使总的代价最小。

这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。

一棵生成树的代价就是树上各边的代价之和。

2图的概念2.1 定义无序积在无序积中，无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。

有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。

有时，泛指有向图或无向图。

2.2 图的表示法有向图，无向图的顶点都用小圆圈表示。

无向边——连接顶点的线段。

有向边——以为始点，以为终点的有向线段。

2.3 概念(1)有限图——都是有限集的图。

阶图——的图。

零图——的图。

特别，若又有，称平凡图。

(2)关联 (边与点关系)——设边(或)，则称与(或)关联。

无环孤立点——无边关联的点。

环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。

悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。

(3)平行边——关联于同一对顶点的若干条边称为平行边。

平行边的条数称为重数。

多重图——含有平行边的图。

简单图——不含平行边和环的图。

2.4 完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称为阶无向完全图，记作。

若有向图的任一对顶点，既有有向边，又有有向边，则称为有向完全图。

例如：3 图的遍历从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次。

这一过程叫做图的遍历。

遍历图的基本方法有两种：深度优先搜索和广度优先搜索。

这两种方法都适用于有向图和无向图。

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条边搜索路径对图中所有顶点各作一次访问。

若给定的图是连通图，则从图中任意顶点出发顺着边可以访问到该图中所有的顶点，然而，图的遍历比树的遍历复杂得多，这是因为图中的任一点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又到了该顶点。

为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。

为此，可设置一个布尔向量visited[1..n],它的初值为false，一旦访问了顶点vi，便将visited[i]置为ture。

3.1基本概念和定理定义定义1:图G=(V,U)的弧列u=(uu..u ) 叫做一个链；把端点重合的链叫做圈，也叫做回路。

定义2:不包含圈的图称为无圈图，连通的无圈图称为树，用符号T 来表示。

定理1:在一棵树中每一对点之间只有一条路径。

定理2:有n个点的一棵树有n-1条边。

定义3:如果一棵树T 为一个连通图的子图，且包括G 中所有的点，则称该树为G 的生成树。

定义4:对每条边e，可赋以一个实数ω(e)，称为e的权，G连同它边上的权称为赋权图。

定义5:在一个加权图中一棵生成树T 的权是T 中各个树枝的权之和，一般而言，加权图G 中不同的生成树将有不同的权，G 的所有生成树中，权最小的那棵生成树称为G的最小生成树，或称为G 的最优生成树。

3.2 连通图的深度优先搜索连通图深度优先搜索的基本思想如下：假定图中某个顶点v1为出发点，首先访问出发点v1，然后任选一个v1的访问过的邻接点v2，以v2为新的出发点继续进行深度优先搜索，直至图中所有顶点被访问过。

显然，图的深度优先搜索是一个递归过程，类似于树的前序遍历，它的特点是尽可能先对纵深方向进行搜索，故称之深度优先搜索。

现以下图中G为例说明深度优搜索过程。

假定v1是出发点，首先访问v1。

因v1有两个邻接点v2、v3均未被访问，选择v2作为新的出发点。

访问v2之后，再找v2的未访问过的邻接点。

同v2邻接的有v1、v4、v5，其中v1以被访问过，而v4、v5未被访问。

选择v4作为新的出发点。

重复上述搜索过程继续依次访问v8、v5。

访问v5之后，由于与v5相邻的顶点均以被访问，搜索退回到v8。

由于v8、v4、v2都没有未被访问的邻接点，所以搜索过程连续地从v8退回到v4，再退回到v2最后退回到v1这时选择v1的未被访问过的邻接点v3，继续往下搜索，依次访问v3、v6、v7，从而遍历了图中全部顶点。

在这个过程中得到的顶点的访问v1→v2→v4→v8→v5→v3→v6→v7这样的序列就称之为图的深度优先搜索遍历序列。

深度优先遍历算法typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1Boolean visited[MaxVertexNum]； //访问标志向量是全局量void DFSTraverse(ALGraph *G){ //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同int i；for(i=0;i<G->n;i++)visited[i]=FALSE； //标志向量初始化for(i=0;i<G->n；i++)if(!visited[i]) //vi未访问过DFS(G，i)； //以vi为源点开始DFS搜索}//DFSTraverse3.3 连通图的广度优先搜索连通图广度优先搜索的基本思想是：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；并使“先被访问的顶点的领接点”先于“后被访问的顶点的领接点”被访问，直至图中所有已经被访问的顶点的领接点都被访问到。

它类似于树的按层次遍历，其特点是尽可能优先对横向搜索，故称之为广度优先搜索。

下面以图中G为例说明广度优先搜索的过程。

首先从起点v1出发，访问v1。

v1有两个未曾访问的邻接点v2和v3。

先访问v2，再访问v3。

然后再先后访问v2的未曾访问过的邻接点v4、v5及v3的未曾访问过的邻接点v6、v7。

最后访问v4的未曾访问过的邻接点v8。

至此图中所有顶点均以被访问到。

得到的顶点访问序列为：v1→v2→v3→v4→v5→v6→v7→v8相应的，这样的序列就称之为图的广度优先搜索遍历序列。

在广度优先搜索中，若对x的访问先于y，则对x邻接点的访问也先于对y的邻接点的访问。

因此，可采用队列来暂存那些刚访问过，但可能还有未访问过的邻接点的顶点。

连通图的广度优先搜索算法如下：void BFS(ALGraph*G，int k){// 以vk为源点对用邻接表表示的图G进行广度优先搜索int i；CirQueue Q； //须将队列定义中DataType改为intEdgeNode *p；InitQueue(&Q)；//队列初始化//访问源点vkprintf("visit vertex：％e"，G->adjlist[k].vertex)；visited[k]=TRUE；EnQueue(&Q，k)；//vk已访问，将其入队。

（实际上是将其序号入队）while(!QueueEmpty(&Q)){//队非空则执行i=DeQueue(&Q)； //相当于vi出队p=G->adjlist[i].firstedge； //取vi的边表头指针while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)if(!visited[p->adivex]){ //若vj未访问过printf("visitvertex：％c"，C->adjlistlp->adjvex].vertex)； //访问 vj visited[p->adjvex]=TRUE；EnQueue(&Q，p->adjvex)；//访问过的vj入队}//endifp=p->next；//找vi的下一邻接点}//endwhile}//endwhile}//end of BFS4 最小生成树的两种经典算法构造最小生成树可以有很多算法。

其中多数算法利用了最小生成树的下列一种简称为MST的性质：假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。

若（u,v）是一条具有最小权值（代价）的边，其中u属于U， v属于U的补集，则必存在一棵包含边（u,v）的最小生成树。

4.1 普里姆(Prim)算法求最小生成树的两种算法中，第一种被称为Prim算法。

它采用的方法是从图G中一条一条地选择边，并将他们加入到支撑树中（1）算法思想假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim 算法通过以下步骤可以得到最小生成树:首先初始化:U={u 0},TE={M}此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的发生变化,直到得到最小生成树为止。

然后在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。

此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。

找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。

这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合。

如果U=V,则算法结束;否则重复步骤2。

可以把本步骤看成循环终止条件。

我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。

（2）Prim算法的伪代码描述PrimMST(G，T，r){//求图G的以r为根的MST，结果放在T=(U，TE)中InitCandidateSet(…)；//初始化：设置初始的最短边候选集，并置T=({r}，￠)for(k=0；k<n-1；k++){ //求n-1条树边(u，v)=SelectLiShtEdge(…)；//选取最短边(u，v)；T←T∪{(u，v)}；//扩充TModifyCandidateSet(…)； }}（3）算法的执行过程用PRIM算法得到最小生成树的过程注意：若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。