最小生成树课程设计.doc

中北大学
数据结构与算法课程设计
说明书
 
学院、系:
软件学院
专业:
软件工程
学生姓名:
xx
学号:
xxx
设计题目:
最小生成树问题

起迄日期:
2013年12月9日- 2013年12月20日
指导教师:
李波
 
 
 2013 年12月 20 日
需求分析
设计内容:给定一个地区的n个城市间的距离网,用prim算法或kruskal算法建立最小生成树,并计算得到的最小生成树的代价。
基本要求:
(1)城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价;
(2)表示城市间距离网的邻接矩阵(要求至少6个城市,10条边);
(3)最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。
2本设计所采用的数据结构
本程序设计所采用的数据结构为图。
3 设计思想
普里姆算法
4 核心代码
int main() //主函数
{ mgraph g; vertextype u; int k;
createUDN(&g); /* 生成邻接矩阵结构的图*/
printf("\nThe graph is:\n");
print(g); /*输出邻接矩阵*/
printf("input the city you want to start:");
scanf("%s",u); /* 输入最小生成树的起点*/
k=locatedvex(g,u);
while(k==-1){
printf("the name of the city is wrong!\n");
printf("input the city you want to start again:");
scanf("%s",u);
k=locatedvex(g,u);
}
minispantree(g,u); /* 普里姆算法求最小生成树*/
}

4 代码
#include""
#include""
#define maxnum 20 /* 图的最大顶点数*/
#define INFINITY 1000 /* 定义一个权值的最大值*/
typedef char vertextype[20]; /*定义城市名称*/
typedef struct ell
{
int adj; /*弧的权值*/
int *info; /*弧上相关信息的指针*/
}ell;
typedef struct array
{
vertextype adjvex; /*顶点的邻接点*/
int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值*/
}array;
typedef struct{
vertextype vexs[maxnum]; /*顶点向量*/
ell arcs[maxnum][maxnum]; /*邻接矩阵*/
int vexnum,um; /*图的顶点个数和弧个数*/
array cl