中北大学
数据结构与算法课程设计
说 明 书
学 院、系： 专 业： 班 级： 学 生 姓 名： 设 计 题 目：
起 迄 日 期: 指 导 教 师:
软件学院 软件工程
学 号： 最小生成树问题
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)
1
初始条件：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
2
#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 /* 邻接表头结点的类型 */
3
{ 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;i
图一
/* 建立无向图的邻接表算法 */ Status InitALGraph(ALGraph *G){
4
最小生成树问题中北大学数据结构课程设计
