数据结构-实验7求最小生成树和最短路径.doc

7.1 采用普里姆算法求最小生成树 实验目的 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 实验内容 7.1 采用普里姆算法求最小生成树 （1）编写一个算法，对于教材图7.16(a)所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。图的存储结构自选。 （2）对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。c.重复b步直至输出n-1条边。） 7.2 采用迪杰斯特拉算法求单源最短路径 编写一个算法，采用迪杰斯特拉算法，输出如下图所示的有向带权图G中从顶点a到其他各顶点的最短路径长度和最短路径。图的存储结构自选 源代码及结果截图 7.1 #includemalloc.h #includestdlib.h #includestdio.h #include windows.h #include limits.h #define MAX_VERTEX_NUM 20 // 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 20 // 相关信息字符串的最大长度+1 #define INFINITY INT_MAX // 用整型最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_NAME]; // 邻接矩阵的数据结构 typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, // 图的当前顶点数 arcnum; // 图的当前弧数 } MGraph; // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct { VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(MGraph G,VertexType u) { int i; for(i = 0; i G.vexnum; ++i) if( strcmp(u, G.vexs[i]) == 0) return i; return -1; } // 采用数组(邻接矩阵)表示法,构造无向网G。 int CreateAN(MGraph *G) { int i,j,k,w,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf(请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) ); scanf(%d%d%d%*c,(*G).vexnum,(*G).arcnum,IncInfo); printf(请输入%d个顶点的值(%d个字符):\n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;++i) // 构造顶点向量 scanf(%s,(*G).vexs[i]); for(i=0;i(*G).vexnum;++i) // 初始化邻接矩阵 for(j=0;j(*G).vexnum;++j) { (*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大 (*G).arcs[i][j].info=NULL; } printf