《数据结构-实验7求最小生成树和最短路径.docx》由会员分享，可在线阅读，更多相关《数据结构-实验7求最小生成树和最短路径.docx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构-实验7求最小生成树和最短路径7.1 采用普里姆算法求最小生成树一，实验目的1 . 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方 法和技能；3 .提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4 .训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所 应具备的科学的工作方法和作风。二，实验内容三，7.1采用普里姆算法求最小生成树(1)编写一个算法，对于教材图7.16 (a)所示的无向带权图G采用普里姆算法 输出从顶点VI出发的最小生成树。图的存储结构自选。(2)对于上图，
2、采用克鲁斯卡尔算法输出该图的最小生成树。(提示:a.先对 边按权值从小到大排序，得有序边集E;为所有顶点辅设一个数组Vset,标记 各顶点所处的连通分量，初始时各不相同。b.依次从E中取出一条边(i, j), 检查顶点i和j是否属于同一连通分量，如是，则重取下一条边;否则，该边 即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的 Vset值都修改为与i的相同。c.重复b步直至输出n-1条边。)7.2 采用迪杰斯特拉算法求单源最短路径编写一个算法，采用迪杰斯特拉算法，输出如下图所示的有向带权图G中从顶 点a到其他各顶点的最短路径长度和最短路径。图的存储结构自选这个W就是本次确定
3、的找到最短路径的顶点for(k=l;kn;k+)(min=MAX;w=0;for(j=2;j=n;j+)if (finalj=0 & djmin)(min=dj;w=j;final w=l ;修改w的标志，说明它已被确定了最短路径了if (w!=0) printf(%5d, w);pw w=l ;pw w为1才表示w这个顶点已是这条最短路径的终点)以下根据dw值以及原di修正其余顶点i的最短路径长度，同时修正P数组值for(i=l;i=n;i+)if (final i-0& (min+edges w i) di)di=min+edgeswi;一旦di被修改，说明到i的路径必经过w这个顶点，因此
4、将w的路径信息复制到i顶点的路径上for(t=l;t=n;t+)pi t=pw t;以下输出单源最短路径和长度及路径信息printf (n);for(i=2;i%d 无最短路径，i);elseprintf (V1-%d: %dnz，, i, di);到顶点 i 的最短路径长度 diprintf (路径：”)；for (j=l; j=n; j+)到顶点i的路径信息就在p的第i行if (pi j=D 说明路径必经过j这个顶点printf(%3d，j);printf(n);void main ()int n;Createedges (&n) ;/*创建一个有n个顶点的图*/di jkstra(Edg
5、es, n) ;/*构造最短路径*/s 21262 3 4b11120 ? 4 4-3517 26 7 4 75 7 3 4 G 6JJr Dm 二二 产产产4LL工箕右霜 耨各ffife( E爵坨 呈mII上耗 用用用用用3 4 r d】 rn 口一工 ”1 I fl lll nt I. Il, I* n. I n 山.山.山山,山.内山-&中 35 :点点点点点A点A息一钻.- -BBS.7i:d:q:oal:d懿 -4正二正|=丘七二LLlgmLIM?t-4 一:寸寸&-/什LfLff一上 t.LtsLI 0 X 6 5 1 4 1 t w 1WC1234、678911 1 2 1 i
6、6-T.gg 以书 Hr 【nrE二RL,M、Mx.qL、:， u Aq. VUJWTIVq1aaaaaaaaw百百百百一、iI 1 t!rf。-7四备役； 13467(ress any key to continue四，实验小结1、通过求最小生成树，进一步掌握了图的含义。知道了普里姆算法。通过本次课程设计，锻炼了我们的实际操作能力，培养了我们严密的思维和严谨的态度。2、 通过此实验，我学会了用普里姆算法求最小生成树和用迪杰斯特拉算法求单源最短路径的方法。四，源代码及结果截图7. 1#include#include#includeftinclude ftincludelimits. h#def
7、ine MAX_VERTEX_NUM 20 / 最大顶点个数 ftdefine MAX_NAME 3 / 顶点 字符串的最大长度+1 define MAX_INF0 20 /相关信息字符串的最大长度+1 #define INFINITY I NT MAX / 用整型最大值代替？ typedef int VRType;typedef char InfoType; typedef char VertexTypeMAX_NAME;/邻接矩阵的数据结构typedef structVRType adj; /顶点关系类型。对无权图，用1 （是）或0（否）表示相邻否;/对带权图，则为权值类型InfoType
8、 *info; 该弧相关信息的指针(可无)ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图的数据结构typedef struct(VertexType vexsMAX_VERTEX_NUM ; / 顶点向量AdjMatrix arcs; / 邻接矩阵int vexnum, 图的当前顶点数arcnum; /图的当前弧数 MGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef struct(VertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM ; /若G中存在顶点u,
9、则返回该顶点在图中位置;否则返回-1。int LocateVex (MGraph G, VertexType u)int i;for(i = 0; i G. vexnum; +i)if ( strcmp(u, G. vexsi) = 0)return i;return -1;/采用数组(邻接矩阵)表示法，构造无向网G。int CreateAN(MGraph *G)int i, j, k, w, Inclnfo;char sMAX_INF0, *info;VertexType va, vb;printf (请输入无向网G的顶点数,边数,边是否含其它信息(是：1,否:0):(空 格区分)；scan
10、f (级d%d%d%*c，& (*G). vexnum, & (*G). arcnum, &lnclnfo);printf (请输入%d 个顶点的值(%d 个字符)：n，(*G). vexnum, MAX_NAME);for (i=0; i (*G). vexnum; +i) / 构造顶点向量scanf(s，(*G).vexsi);for (i=0; i(*G). vexnum;+i) / 初始化邻接矩阵for(j=0;j(*G), vexnum;+j)(*G). arcsi j. adj=INFINITY; / 网初始化为无穷大(*G). arcsij. info二NULL;printf (
11、请输入%d条边的顶点1、顶点2、权值(以空格作为间隔)：n，(*G). arcnum);for(k=0;k(*G). arcnum;+k)scanf (s%s%d%*c, va, vb, &w) ; / %*c 吃掉回车符i二LocateVex(*G, va);j=LocateVex(*G, vb);(*G). arcsi j. adj=(*G). arcsj i. adj=w; / 无向if(Inclnfo)printf (请输入该边的相关信息个字符)：,MAX_INFO);gets(s);w=strlen (s);i f (w)info二(char*)malloc(w+1)*sizeof(
12、char);strcpy (info, s);(*G) arcsi j. info=(*G). arcsj i. info=info; / 无向return 1;/求closedge. lowcost的最小正值int minimum(minside SZ, MGraph G) int i=0, j, k, min;while(!SZi. lowcost)i+；min=SZi. lowcost; / 第一个不为 0 的值k=i；for(j=i+l；j0)if(minSZj. lowcost)(min=SZj. lowcost;k=j；return k;/用普里姆算法从第U个顶点出发构造网G的最小
13、生成树T,输出T的各条边 void MiniSpanTree_PRIM(MGraph G,VertexType u)(int i, j, k;minside closedge;k=LocateVex(G, u);for (j=0; jG. vexnum; +j) / 辅助数组初始化if(j!=k)(strcpy(closedgej. adjvex,u);closedgej. lowcost=G. arcskj. adj;closedgek. lowcost-0; / 初始,U=uprintf (最小代价生成树的各条边为:n);for(i=l;iG. vexnum;+i) /选择其余G. vex
14、numT个顶点k=minimum(closedge, G) ; /求出T的下一个结点：第K顶点printf (s-%s八n, closedgek. adjvex, G. vexsk) ; / 输出生成树的边closedgek. lowcost=0; / 第 K 顶点并入 U 集for(j=0;jG. vexnum;+j)if(G. arcskj. adj;品江;蕨边露点、M点2、权值。泛招隹为同牌； ul u2 6 “u4 S “u3 X u2 v3 G s2 vS ) “3 3 5 心“5 G 3 vG 4 p4 v6 2匐点生蹄书冶柒边为KCu1-v3 Kv3-u$ kvfe-v4 (u3
15、-Z (u2-u! 谓按年京世茹续7.2ftinclude ftinclude #define M 30define MAX 200int Edges M M ;/存放权的二维数组void Createedges (int *n) int i, j, w, e;int b, t;printf (请输入点数和边数(中间用空格隔开)：)；scanf (z，%d %d，n, &e);for(i=l;i=*n;i+)for(j=l;j=*n;j+)Edgesij=MAX; 所有边的权初始化为最大for(i=l;i=e;i+)printf(请输入第%d条边上的信息:起点、终点及权值(中间用空格隔开):
16、，i);scanf (d %d %d，&b, &t, &w);Edgesbt=w;/Edgesl2=15;Edgesl3=2;Edges14=12;Edges25=6;Edges7 二4/ Edges57=9;Edges35=8;Edges36=4;Edges47=3：Edges64=5;Edges67=10void di jkstra(int edgesM M, int n) int dM;存放最短路径的长度 int finalM = 0;存放已确定最短路径的顶点的标志，为1说明已确定为0 说明还未确定int pM M = 0 ;p数组开始全部为0int i, j, k, t, m, min, w;初始化数组d, final以及p for(i=l;i=n;i+) di=edgesl i;finali=0;for(j=l;j=n;j+) pi j=0;if (diMAX)pi 1=1 ；以下循环共执行n-1次，每次都是在所有未确定最短路径的顶点v的dv中 找一个最小值以及位置W