7.1 采用普里姆算法求最小生成树
一， 实验目的
1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二， 实验内容
三， 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
#include
#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(
printf(请输入%d个顶点的值(<%d个字符):\n for(i=0;i<(*G).vexnum;++i) // 构造顶点向量 scanf(
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(请输入%d条边的顶点1 、顶点2、 权值(以空格作为间隔): \n
for(k=0;k<(*G).arcnum;++k) {
scanf(吃掉回车符 i=LocateVex(*G,va); j=LocateVex(*G,vb);
…… 此处隐藏785字 ……
7.2
#include
int Edges[M][M]; //存放权的二维数组 void Createedges(int *n) {
int i,j,w,e; int b,t;
printf(请输入点数和边数(中间用空格隔开）： scanf( for(i=1;i<=*n;i++) for(j=1;j<=*n;j++)
Edges[i][j]=MAX; //所有边的权初始化为最大
for(i=1;i<=e;i++)