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

实验报告
June 18
2015
：斌 学号：E11314079 专业：13计算机科学与技术
数据结构 第八次实验
学号 E11314079 专业 计算机科学与技术 斌
实验日期 教师签字 成绩
实 验 报 告
【实验名称】 最小生成树和最短路径
【实验目的】
掌握最小生成树以及最短路径的相关概念；
掌握Prim算法和Kruskal算法；
掌握Dijkstra算法
【实验容】
采用普里姆算法求最小生成树
编写一个算法，(a)所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。图的存储结构自选。
对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。-1条边。）
源代码：
:
#include<>
#include<>
#include<> //malloc( )
#include<> // INT ,MAX
#include<> //EOF,NULL
#include<> //atoi( )
#include<> //eof( )
#include<> //floor( ),ceil( ),abs( )
#include<> //exit( )
#include<> //cout,cin
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//OVERFLOW 在 中已定义为3
typedef int Status;
typedef int Boolean; // 布尔类型
:
#include""
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef char VertexType[MAX_NAME];
/*图的数组(邻接矩阵)存储表示 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<;++i)
if(s