中北大学
数据结构与算法课程设计
说明书
学院、系：软件学院
专业：软件工程
班级：
学生姓名：学号：
设计题目：最小生成树问题
起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟
2015 年1月 29 日
1需求分析
1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。
1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。
1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。
1.4程序通过人机交互实现数据的输入和输出。
2选题要求
设计内容：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。
设计要求：
(1) 符合课题要求，实现相应功能；
(2) 要求界面友好美观，操作方便易行；
(3) 注意程序的实用性、安全性。
3程序设计方法及主要函数介绍
ADT Graph{
数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R = {VR}
VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P;
CreateMGraph(MGraph *G)
初始条件：V是图的顶点集，VR是图的边的集合。
操作结果：按V和VR的定义构造图G，用邻接矩阵存储。
CreateALGraph(ALGraph *G)
初始条件：V是图的顶点集，VR是图的边的集合。
操作结果：按V和VR的定义构造图G，用邻接表存储。
LocateVex（G，u）
初始条件：图G存在，u和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
MiniSpanTree_PRIM（G, u)
初始条件：图G存在，u是图G中的一个顶点。
操作结果：用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
Kriuskal(G)
初始条件：图G存在
操作结果：用克鲁斯卡尔算法构造图G的最小生成树T，输出T的各条边。
ListToMat(MGraph *G1,ALGraph *G2)
初始条件：图G2存在
操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图G1表示。
MatToList(MGraph *G1,ALGraph *G2)
初始条件：图G1存在
操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图G2表示。
LocateVex(MGraph *G,VertexType u)
初始条件：图G存在，u和G中顶点有相同特征
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
}ADT Graph
4程序源代码（包括注释）
#include
#include
#include
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -1
#define INFEASIBLE -2
typedef int Status;
#define INFINITY 0
#define MAX_VERTEX_NUM 20
#define MAX_NAME 5
typedef char VertexType[MAX_NAME];
typedef int VRType;
typedef struct ArcCell
{
VRType adj;
/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/
/*对带权全图，则为权值类型*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM];
/*顶点向量*/
AdjMatrix arcs;
/*邻接矩阵*/
int vexnum,arcnum;
/*图的当前顶点数和弧数*/
}MGraph;
/* 以下定义邻接表类型 */
typedef struct ANode /* 弧的结点结构类型 */
{ int end;
int begin; /* 该弧的终点位置 */
int weight; /* 该弧的相关信息,这里用于存放权值 */ struct ANode *nextarc; /* 指向下一条弧的指针 */
}ANode;
typedef struct VNode /* 邻接表头结点的类型 */
{ VertexType vertex; /* 顶点信息 */
int bianhao;
ANode *firstarc; /* 指向第一条弧 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* AdjList是邻接表类型 */
typedef struct ALGraph
{ AdjList adjlist; /* 邻接表 */
int vexnum,arcnum; /* 图中顶点数n和边数 e */
}ALGraph; /* 图的邻接表类型 */
int LocateVex(MGraph *G,VertexType u)
{ /*初始条件：图G存在，u和G中顶点有相同特征*/
/*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/ int i;
for(i=0;ivexnum;++i)
if(strcmp(u,G->vexs[i])==0)
return i;
return -1;
}
图一
/* 建立无向图的邻接表算法 */
Status InitALGraph(ALGraph *G){
