贪心算法最小生成树

摘要

网络的最小生成树在实际中有广泛的应用，例如，网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。本课程设计采用贪心算法中Prim算法解决最小生成树问题，贪心算法包括两个基本要素：最优子结构性质和贪心选择利性质，贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。通过分析用贪心算法解决最小生成树问题能得到问题的最优解。

根据算法的设计结果，采用C++语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。

关键词：最小生成树，贪心算法

1 问题描述.................................................................................................................... 1

2 问题分析.................................................................................................................... 2

3 建立数学模型............................................................................................................ 3

4 算法设计.................................................................................................................... 5

5 算法实现.................................................................................................................... 6

6 测试分析.................................................................................................................. 12

结论.......................................................................................................................... 13

参考文献...................................................................................................................... 14

1 问题描述

设图G=(V，E)是一简单连通图，|V|=n，|E|=m，每条边ei都给以权wi，wi假定是边ei的长度（其他的也可以），i=1，2，3，„，m。求图G的总长度最短的树。首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈v-s，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

2 问题分析

首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈v-s，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种“贪心”的策略。

该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。基本思想：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。

当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要O(e)时间，在上述算法的while循环中，DeleteMin运算需要O(loge)时间，因此关于优先队列所作运算的时间为O(eloge)。实现UnionFind所需的时间为O(eloge)或O(elog*e)。所以Kruskal算法所需的计算时间为O(eloge)。

当e=Ω(n2)时，Kruskal算法比Prim算法差，但当e=O(n2)时，Kruskal算法却比Prim算法好得多。Kruskal算法的时间主要取决于边数。它较适合于稀疏图。

3 建立数学模型

1 . 在编译时，出现有些库函数没有定义和警告错误；

解决方法：需要在程序首部加入以下包含文件：#include"stdio.h"、#include"string.h"、#include"malloc.h"、#include "iomanip.h"；出现的警告错误是由于定义一指针变量时，需用库函数malloc（）为其分配内存空间 2 . 在创建无向网函数creat()中，当输入的顶点个数

解决方法：通过在函数首部定义一标记变量flag，将其初始化为0，当输入的顶点个数>v1>>v2>>weight; ” 输入边所关联的两个顶点和权值；

3 . 在函数Minium()中，当用语句“min=close[0].lowcost”初始化min时，会导致结果出现错误；

解决方法：用语句“min=INFINIT;”可以将其置为∞；

4. 在普里姆算法函数prim()，如何将最小生成树中的顶点序列显示出来；

解决方法：首先，定义AdjMatrix结构体类型的指针变量*p，并通过语句“p->vexs[n++]=u;”将起点存入顶点向量表中，然后在for循环体中用语句“p->vexs[n++]=v0;”将每条边的终点依次放入顶点向量表中，最后向量表中的数据就是最小生成树中的顶点序列，通过fou循环将其输出；

5. 在输出邻接矩阵函数display()中，如何将矩阵中值为INFINIT的元素在屏幕上用∞显示；

解决方法：通过if判断语句“if(G->arcs[i][j].adj==INFINIT) cout

6 . 在主函数main()中，当前一次创建网时输入的顶点个数1时，此时若求最小生成树时，得到的结果将出错。

解决方法：需在main()函数的第一层while()循环体的最后加入语句“flag=0;”，因为在创建函数creat()中，当第一次创建网时输入的顶点个数1时，由于flag此时为1，所以仍将其按照第一种情况处理，从而导致结果出错；

4 算法设计

1.输入网中的顶点数。您可以输入在定义范围之内的任意值，当输入的顶点数

2.请输入网中的边数。根据用户自己定义

3.请输入网中的顶点编号。分别输入网中的所有顶点

4.输入每条弧所对应的两个顶点及权值。分别输入起点、终点和权值，输入时两者之间以空格隔开

5.请输入起点。输入从网中的哪个顶点出发，生成最小生成树，可以输入网中的任意顶点，若输入的起点不是网中的某一顶点则显示“输入起点有错，请重新输入!”若想退出此操作则输入0

6.继续创建无向网请输入'Y',否则按任意键。如果用户想再次创建网并做相关操作，则输入‘Y’或‘y’否则输入任意字符退出运行环境

5 算法实现

#include"stdio.h"

#include"string.h"

#include"malloc.h"

#include"iostream.h"

#include "iomanip.h"

#define MAX 20 //最多顶点个数

#define INFINIT 32768//表示极大值，即∞

typedef struct

{int adj; //adj是权值类型

}ArcNode;

typedef struct

{int vexs[MAX],vexnum,arcnum;

/*vexs表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ ArcNode arcs[MAX][MAX]; /*邻接矩阵*/

}AdjMatrix;

typedef struct

{int adjvex;//存放顶点编号

int lowcost;//存放顶点权值

}Node;

Node close[MAX];//求最小生成树时的辅助数组

int flag=0;

int Locate(AdjMatrix *G,int V) //求顶点位置函数

{int j=-1,k;

for(k=0;kvexnum;k++)

if(G->vexs[k]==V) {j=k;break;}

return j;

AdjMatrix *creat(AdjMatrix *G) //创建无向网

{int i,j,k,v1,v2,weight,m=1;

printf("请输入网中的顶点数：");

scanf("%d",&G->vexnum);

if(G->vexnum

{cout

flag=1;

return G;

}

else

{printf("请输入网中的边数：");

scanf("%d",&G->arcnum);

for(i=0;ivexnum;i++) //初始化邻接矩阵

for(j=0;jvexnum;j++)

if(i==j) G->arcs[i][j].adj=0;

else G->arcs[i][j].adj=INFINIT;

printf("请输入网中的顶点编号："); //输入网中的顶点编号

for(i=0;ivexnum;i++)

scanf("%d",&G->vexs[i]);

printf("输入每条弧所对应的两个顶点及权值!\n");

for(k=0;karcnum;k++)

{ cout

cin>>v1>>v2>>weight; //输入一条弧的两个顶点及权值 i=Locate(G,v1);

j=Locate(G,v2);

G->arcs[i][j].adj=weight;

G->arcs[j][i].adj=weight;

return(G);

}}

int Minium(AdjMatrix *G,Node close[])//close[]中权值最小的边 {int i,min,k;

min=INFINIT;//置最小权值为INFINIT

for(i=0;ivexnum;i++)

if(close[i].lowcost

{min=close[i].lowcost;k=i;}

return k;//返回权值最小的边在辅助数组中的位置

}

void prim(AdjMatrix *G,int u)//普里姆算法

//从顶点u出发,按普里姆算法构造连通网G的最小生成树，并输出生成树的每条边

{int i,j,k,k0,u0,v0,s=0,n=0;

AdjMatrix *p;

p=(AdjMatrix *)malloc(sizeof(AdjMatrix));

k=Locate(G,u);//k为顶点u的位置

p->vexs[n++]=u;

close[k].lowcost=0;//初始化U={u}

for(i=0;ivexnum;i++)

if(i!=k) //对V-U中的顶点i,初始化close[i]

{close[i].adjvex=u;

close[i].lowcost=G->arcs[k][i].adj;

}

for(j=1;jvexnum-1;j++)//找n-1条边(n=G->vexnum)

{ k0=Minium(G,close);//close[k0]中存有当前最小边(u0, v0)的信息 u0=close[k0].adjvex;//u0∈U

v0=G->vexs[k0]; //v0∈V-U

p->vexs[n++]=v0;//将终点放入数组中

s+=close[k0].lowcost;//求最小生成树的权值之和

cout

路径

close[k0].lowcost=0;//将顶点v0纳入U集合

for(i=0;ivexnum;i++)//在顶点v0并入U之后,更新closedge[i]

if(G->arcs[k0][i].adj

{close[i].lowcost=G->arcs[k0][i].adj;

close[i].adjvex=v0;

}

cout

for(i=0;ivexnum;i++) coutvexs[i]

cout

void display(AdjMatrix *G) //输出邻接矩阵算法

{int i,j;

for(i=0;ivexnum;i++)

coutvexs[i];

cout

for(i=0;ivexnum;i++)

cout

for(i=0;ivexnum;i++)

{

coutvexs[i]

for(j=0;jvexnum;j++)

if(G->arcs[i][j].adj==INFINIT) cout

else coutarcs[i][j].adj;

cout

}

for(i=0;ivexnum;i++)

cout

}

void main() //主函数

{ char ch;

int st;

AdjMatrix *G,*p;

p=(AdjMatrix *)malloc(sizeof(AdjMatrix));

cout

endl;

cout

键!**************************"

cin>>ch;

while(1)

if(ch=='Y'||ch=='y')

{ G=creat(p);

if(flag==0)

{ cout

***********"

display(G);

cout

cin>>st;

while(1)

{if(st==0) break;

else if(st>G->vexnum)

cout

入!------------------------------"

else

{cout

cout

cout终点> 权值"

prim(G,st);

cout

}

cout

cin>>st;

}

cout

键!**************************"

cin>>ch;

flag=0;

}

else break;

}

6 测试分析

在本程序中用存储边（带权）的数组表示图，而不是用邻接矩阵的数组表示法或邻接表。为了让读者能一目了然看清结果，在终端输出从顶点0开始的最短路径时，设置了输出值的宽度。为了简便起见，程序中的顶点、边的权值都设置成了整形，顶点的标记从0开始用数字代替城市名称。在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。由于克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，构造最小生成树的时间复杂度为O(eloge)，e为网中边的数目，所以其时间复杂度与边有关，它适用于稀疏图。普里姆算法也是求最小生成树的基本算法，其时间复杂度为O(n2)，与网中的边数无关，而与定点数关，故其适用于求边稀疏的网的最小生成树。所以说，两种算法各有优势。

结论

整个课程设计的过程中，首先，应该根据课题的要求对题意进行分析，将所遇到的问题进行归纳和总结，在本设计中，题意要求对给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树，我们应该了解关于网的一些基本概念和生成树与最小生成树之间有何区别和联系，主要是要明确的理解PRIM算法的基本思想。其次，针对出现的问题查找相关资料将其解决，主要应该查找有关PRIM算法基本思想方面的详细介绍，当所有的问题得到解决后，对本设计应该有个整体的思路并通过编写各个函数模块去实现课题的功能；最后，将编写的源程序代码在计算机上调试运行，直至调试成功。

参考文献

[1]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007.

[2]余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:华中科技大学出版社,2000．

[3]卢开澄.计算机算法导引—设计与分析[M].北京:清华大学出版社,2003．

[4] M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京电子工业出版社.

[5谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006

[6] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997．