最小生成树的Prim算法提高型实验报告

1、黄冈师范学院提高型实验报告实验课题最小生成树的Prim算法（实验类型：口综合性 设计性 应用性）实验课程算法程序设计实验时间2010年12月24日学生姓名周媛鑫专业班级计科0801学 号 200826140110实验目的和要求根据算法设计需要，掌握连通网的灵活表示方法；掌握最小生成树的Prim算法；熟练掌握贪心算法的设计方法；实验条件硬件环境：实验室电脑一台软件环境：winTC实验原理分析最小生成树的定义：假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1 条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路， 其中网的顶点表示城市，边表示两地间的线路，赋

2、于边的权值表示相应的代价。 对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一 个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小 生成树。构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面 一种简称为MST的性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非 空子集。若(u,v)是一条具有最小权值(代价)的边，其中uU，veV-U，则必 存在一棵包含边(u.v )的最小生成树。普里姆(Prim)算法即是利用MST性质构造最小生成树的算法。算法思想 如下：假设N=(V,E)和是连通网，TE是N上最小生成树中边的集合。算法从U=u0(

3、u0 eV)，TE=(开始，重复执行下述操作：在所有ueU，veV-U的边(u, v) eE 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入。，直到U=V为止。 此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。实验步骤数据结构的设计：采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作：邻接矩阵的抽象数据结构定义：#define INFINITYINT_MAX/最大值#defineMAX_ERTEX_NUM20/最大顶点数typedef enum DG,DN,UDG,UDNGraphKind;/有向图，有向网，无向网，无向图 typedef struct Arc

4、 Cell(VRType adj ; / VRType是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info;/该弧相关信息的指针ArcCell ， AdjMatrix MAX_VERTEX_NUMMAX_VERTEX_NUM；Typedef struct (VertexType vexs MAX_VERTEX_NUM;顶点向量AdjMatrix arcs ; int vexnum , arcnum GraphKind kind ; Mgraph ;函数设计AdjMatrix arcs ; int vexnum , arcnum GraphKind kind ; Mgra

5、ph ;函数设计/邻接矩阵图的当前顶点数和弧数/图的种类标志函数名称函数原型功能描述main() int main(void) 系统调用主函数Huiru() void Huitu () 绘制无向图GraphicVer() void GraphicVer(Graph *G) 输出邻接矩阵 prim() void prim(Graph *G) PRIM 算法演示实验源代码#include#include #include #include #include #define MaxVertexNum 50#define INF 32767typedef struct Graphic(char vex

6、sMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int v,e;Graph;char tmp10;void Huitu() /*无向图的图形生成*/(char buffer100;int graphdriver = DETECT, graphmode;int i,xbefore,ybefore;int x1,y1; char c;/*registerbgidriver(EGAVGA_driver);initgraph(&graphdriver, &graphmode, ); cleardevice();printf(input pot (300

7、x610,yv,&G-e);for(i=1;iv;i+)for(j=1;jv;j+)if(i=j) G-edgesij=0;else( G-edgesij=INF;for(k=1;ke;k+)printf(input %dth edge :,k);scanf(%d,%d,%d,&v1,&v2,&weight);G-edgesv1v2=G-edgesv2v1=weight;for(i=1;iv;i+)printf(n)；for(j=1;jv;j+)printf(G-edgesij=INF)?8t：dt，G-edgesij); printf(n)；system(pause)；/*prim 算法生成

8、最小生成树*/void prim(Graph *G)(int lowcostMaxVertexNum,closestMaxVertexNum;int i,j,k,min;for(i=2;iv;i+)/*n 个顶点，n-1 条边 */(lowcosti=G-edges1i;closesti = 1;lowcost1=0;/*标志顶点1加入U集合*/for(i=2;iv;i+)/*形成 n-1 条边的生成树 */(min=INF; k=0;for(j=2;jv;j+)if(lowcostjmin)&(lowcostj!=0)(min=lowcostj; k=j;printf(%d,%d)%2dt,

9、closestk,k,min);lowcostk=0;/*顶点 k 加入 U*/for(j=2;jv;j+)/*修改由顶点k到其他顶点边的权值*/if(G-edgeskjedgeskj;closestj=k;printf(n)；void drawwapicture(int lowcost口，int closest口，int vex)( int i=0,x=0,datax=0;setviewport(150,140,630,310,1);cleardevice();setcolor(GREEN);rectangle(10,10,470,160);line(10,60,470,60);line(1

10、0,110,470,110);for(i=0;ivex;i+)(x=470-40*i;datax=470-20*i;line(x,10,x,160);if(vex-i)!=0)outtextxy(datax,35,(vex-i)0)；vsprintf(tmp,d，&lowcostvex-i);outtextxy(datax,85,tmp);vsprintf(tmp,d，&closestvex-i);outtextxy(datax,135,tmp);elseouttextxy(datax,35,i0)；outtextxy(datax,85,lowcost0)；outtextxy(datax,13

11、5,closest0);getche();closegraph();/*prim 算法生成最小生成树*/void primyanshi(Graph *G)( void drawwapicture(int *p,int*q,int k);int lowcostMaxVertexNum,closestMaxVertexNum;int i,j,k,min;cleardevice();for(i=2;iv;i+)/*n 个顶点，n-1 条边 */( lowcosti=G-edges1i;/* 初始化 */closesti = 1; /*顶点未加入到最小生成树中*/drawwapicture(lowco

12、st,closest,G-v);lowcost1=0;drawwapicture(lowcost,closest,G-v);for(i=2;iv;i+)/*形成 n-1 条边的生成树 */(min=INF; k=0;for(j=2;jv;j+)if(lowcostjv);cprintf(%d,%d)%2dt，closestk,k,min);lowcostk=0;/*顶点 k 加入 U*/drawwapicture(lowcost,closest,G-v);for(j=2;jv;j+)/*修改由顶点k到其他顶点边的权值*/if(G-edgeskjedgeskj;closestj=k;drawwa

13、picture(lowcost,closest,G-v);printf(n)；int main()(Graph *G=NULL;int flag=1;printf(/*/n)；printf(/*Welcome to the world of IRIS*/n);printf(/*200826140110*/n)；while(flag!=0)(printf(1:Build a Undigraph Net and output the adjMatrix.n)；printf(2.Output the Mini_tree:n)；printf(3.Display the procession of Mi

14、ni_tree with PRIM:n)；printf(4.exit:n)；scanf(%d,&flag);switch(flag)(printf(%d,flag);case 1:Huitu();GraphicVer(G);break;case 2:prim(G);break;case 3: primyanshi(G);break;default :printf(Thank you!n)；system(pause)；exit(0);printf(Thank you!n)；system(pause)； return 0;五.实验结果分析1th edjE：: 2li edljg- 3th巳的日：

15、1th edjE：: 2li edljg- 3th巳的日： 4th edge : 5th edge : JobTTTte datajwst pirtare nos in the cotruters memory.md ue reed hnu it pneimoy and ulietJier it ha雪 the correct data.33廿95 Q TOC o 1-5 h z 0西7B33廿95 Q45C16?eit03S G 95ITie 1th search to FinA tie min Yig砒 in the locust is the (1339Singnud i)ic iawi

16、rstCil-c IcsEstCU =0Zarrect Hie 1 aucDst? uiili Ihe sim 1 ier is-tance Letueen 4th dot and othen dots I hat is not be ffiqned.e 的 花。 i idn you cutcPi me 7六.实验小结通过此次实验后我深刻地学习了最小生成树的Prim算法，通过分析实验目 的和实验内容；阐述不同方法的原理；分析不同方法的特点和区别以及时空复杂 度；分析和调试测试数据和相应的结果.明白了 Prim算法是设计思想：设图G = (V, E),其生成树的顶点集合为U。把v0放入队；在所有ueu, vey-U的边 (u,v) eE中找一条最小权值的边，加入生成树；把找到的边的v加入U集合。 如果U集合已有n个元素，则结束，否则继续执行。Prim算法实现：一方面 利用集合，设置一个数组set(i=0,1,.,n-1),初始值为0,代表对应