最小生成树与最短路径 数据结构 报告.doc

《最小生成树与最短路径 数据结构 报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告姓名：张珂瑈班级：rJBJava102学号：201007092213指导老师：杨关时间：2012年6月13日10第页，共10页软件学院实验报告院、系：软件学院姓名张珂瑈学号201007092213专业、班级软件工程、rJBJava102课程名称数据结构实验室名称2#101实验名称最小生成树与最短路径指导老师杨关日期、时间2012年6月12日，下午第一节课同组者无天气晴室（气）温 20℃实验报告内容：1．实验目的：通过本次试验，熟练掌握图的相关操作2．实验程序清单：2.1最小生成树#include#defineINFINITYINT

2、_MAX/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM26/*最大顶点个数*/structedges/*边集类型，存储一条边的起始顶点bv、终止顶点tv和权w*/{intbv,tv,w;};typedefstructedgesedgeset[MAXEDGE];intseeks(intset[],intv){inti=v;10第页，共10页while(set[i]>0)i=set[i];return(i);}kruskal(edgesetge,intn,inte)/*ge表示的图是按权值从小到大排列的*/{intset[MAXEDGE],v1,

3、v2,i,j;for(i=1;i<=n;i++)set[i]=0;/*给set中的每个元素赋初值*/i=1;/*i表示待获取的生成树中的边数，初值为1*/j=1;/*j表示ge中的下标，初值为1*/while(j

4、[i].tv);set[v1]=v2;j++;}i++;}}voidmain(){intn=7,e=10;edgesetmx;mx[1].bv=4;mx[1].tv=6;mx[1].w=30;mx[2].bv=2;mx[2].tv=5;mx[2].w=40;mx[3].bv=4;mx[3].tv=7;mx[3].w=42;mx[4].bv=3;mx[4].tv=7;mx[4].w=45;mx[5].bv=1;mx[5].tv=2;mx[5].w=50;mx[6].bv=4;mx[6].tv=5;mx[6].w=50;mx[7].bv=3;mx[7].tv=4;mx

5、[7].w=52;10第页，共10页mx[8].bv=1;mx[8].tv=3;mx[8].w=60;mx[9].bv=2;mx[9].tv=4;mx[9].w=65;mx[10].bv=5;mx[10].tv=6;mx[10].w=70;printf("最小生成树边集：");kruskal(mx,n,e);}2.2最短路径#include#definen5  //结点数目#definemaxsize160 //表示两点间不可达intpath[n][n];//路径矩阵voidfloyd(intA[][n],intC[][n]); //A是路径

6、长度矩阵，C是有向网络G的带权邻接矩阵voidmain(){ printf("              ——所有顶点对之间的最短路径：Floyd算法——"); printf("（160为无穷远，不可达）"); int10第页，共10页A[n][n],C[n][n]={  {0,10,maxsize,30,100},  {maxsize,0,50,maxsize,maxsize},  {maxsize,maxsize,0,maxsize,10},  {maxsize,maxsize,20,0,60},  {maxsize,maxsize,maxsize,m

7、axsize,0} }; floyd(A,C);}voidfloyd(intA[][n],intC[][n]) //A是路径长度矩阵，C是有向网络G的带权邻接矩阵{ inti,j,k,next; intmax=160; for(i=0;i

8、试图将顶点