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

《最小生成树的prim算法提高型实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、黄冈师范学院提高型实验报告实验课题最小生成树的Prini算法（实验类型：□综合性■设计性□应用性）实验课程算法程序设计实验时间2010年12刀24日学生姓名周媛鑫专业班级计科080]学号200826140110一.实验目的和要求(1)根据算法设计需要，掌握连通网的灵活表示方法;(2)掌握最小生成树的Prim算法；(3)熟练掌握贪心算法的设计方法；一.实验条件(1)硬件环境：实验室电脑一台(2)软件环境:winTC二.实验原理分析(1)最小生成树的定义：假设一个单位要在n个办公地点之间建立通信网，则连通

2、n个地点只需要n-l条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路,其屮网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。(2)构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)

3、的边，其中ueu,vGV-U,则必存在一棵包含边(u.v)的最小生成树。(3)普里姆(Prim)算法即是利用MST性质构造最小生成树的算法。算法思想如下：假设N=(V,{E})和是连通网,TE是N上最小生成树屮边的集合。算法从U={uO}(uOeV),TE二{}开始，重复执行下述操作：在所有ueu,vev-U的边(u,v)eE中找一条代价最小的边(uO,vO)并入集合TE,同时vO并入U,直到U二V为止。此时TE中必有n-1条边，则T二(V,{TE})为N的最小牛成树。三.实验步骤(1)数据结构的设计

4、:采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作：邻接矩阵的抽象数据结构定义：ttdcfineINFINITYINT_MAX//最大值★defineMAX_ERTEX_NUM20//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向网，无向图}typedefstructArcCell{VRTypeadj;//VRType是顶点关系的类型。对无权图用1和0表示相邻否；InfoTypc*info;//该弧相关信息的指针}ArcCell,Ad

5、jMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；Typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}Mgraph;功能描述系统调用主函数绘制无向图(1)函数设计函数名称函数原型main()intmain(void)Huiru()voidHuitu()GraphicVer()voi

6、dGraphicVer(Graph*G)输岀邻接矩阵prim()voidprim(Graph*G)PRIM算法演示(2)实验源代码#include#includeJtincludcttinclude^include#defineMaxVertexNum50^defineTNF32767typcdcfstructGraphic{charvexs[MaxVertexNum];intedges[MaxVert

7、exNum][MaxVertexNum];intv,e;}Graph;chartmp[10];voidIluituO/*无向图的图形生成*/{charbuffer[100];intgraphdriver=DETECT,graphmode;inti,xbefore,ybefore;intxl,yl;charc;/^rcgistcrbgidrivcr(EGAVGA_drivcr);initgraph(&graphdriver,&graphmode,“");cleardevice();printf(，zin

8、putpot(300