普里姆算法生成最小生成树课程设计毕设论文.doc

JINGCHU UNIVERSITY OF TECHNOLOGY

《数据结构（C语言描述）》
课程设计

学 院 计算机工程学院
班 级 12级软件技术1班
学 号 2012304040122、120
124、133、121
学生姓名 周鑫、王彬彬、李松平
张圣玮、魏远迎
指导教师 余云霞

2014年 1月3日

目 录

1 课程设计介绍 1
1.1 课程设计内容 1
1.2 课程设计要求 1
2 课程设计原理 2
2.1 课设题目粗略分析 2
2.2 原理图介绍 3
2.2.1 功能模块图 3
2.2.2 流程图分析 3
3 数据结构分析 10
3.1 存储结构 10
3.2 算法描述 12
4 调试与分析 22
4.1 调试过程 22
4.2 程序执行过程 22
参考文献 28
附 录 28

1 课程设计介绍
1.1 课程设计内容
编写算法能够建立带权图，并能够用Prim算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
1.2 课程设计要求
1. 可以输入顶点、边数及各路径的权值；
2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表；
3. 可以输出建立的最小生成树；
4. 画出流程图，且函数有必要说明、注释；
5. 课设完成后上交报告及核心代码。

第 28 页 共 29页

2 课程设计原理
2.1 课设题目粗略分析
根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：
1. 创建网图并确定网图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构，方便以后的编程。
2.Prim算法。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。其思想是：令集合U的初值为U{u0}（即假设构造最小生成树时从结点u0开始），集合T 的初值为T={}。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。
2.2 原理图介绍
2.2.1 功能模块图
显示菜单进行选择
选择创建（有）无向图及存储方式
有向图邻接矩阵
无向图邻接矩阵
有向图邻接表
无向图邻接表
调用普里姆算法输出最小生成树
结束
开始
图2.1 功能模块图
2.2.2 流程图分析
1. 主函数
开始
显示菜单，选择输入1或2
选择1
选择2
调用createAgraph()函数
结束
选择1
调用CreateGraph()函数
选择2
调用CreateMGraph()函数
调用createALgraph()函数
调用Prim函数，输出最小生成树

图2.2 主函数流程图

2. CreateMGraph()函数
开始
int i,j,k
for(i=0;i<G->n;i++)
scanf(“\n%c”,&(G->vexs[i]));

for(i=0;i<G->n;i++)
for(j=0;i<G->n;i++)

i=j
G->edges[i][j]=0;
Y
N
G->edges[i][j]=max;
for (k=0;k<G->e;k++)
scanf("\n%d,%d,%d",&i,&j,&weight);
G->edges[i][j]=weight;
OutPut(G);
prim(G->edges,G->n,G->vexs);

结束

图2.3 CreateMGraph()函数流程图

3．Prim()函数
开始
int i,j,k,lowcost[100],mincost;
for(i=1;i<n;i++)
{ lowcost[i]=gm[0][i];
closevertex[i]=0; }

set[i]=0;
i=1;
j=1;
Y
Y

lowcost[0]=0;
closevertex[0]=0;
for(i=1;i<n;i++)
mincost=max;
j=1;
k=1;
j<n
lowcost[j]<mincost&&lowcost[j]!=0
mincost=lowcost[j];
k=j;
j++;
N

N

printf("顶点的序号=%d 边的权值=%d\n",k,mincost);
lowcost[k]=0;

for(j=0;j<n;j++)
gm[k][j]<lowcost[j]
lowcost[j]=gm[k][j]; closevertex[j]=k;
结束

图2.4 Prim()函数流程图

4. createALgraph()函数
开始

int i,j,k,w;
edgenode *s;

scanf("%d,%d%*c",&(g->n),&(g->e));

for(i=0;i<g->n;i++)

scanf("%d",&(g->adjlist[i].vertex));
g->adjlist[i].firstedges=NULL;

for(k=0;k<g->e;k++)

scanf("%d,%d,%d",&i,&j,&w);

s=(edgenode*)malloc(sizeof(edgenode));

s->adjvex=j;
s->weight=w;
s->next=g->adjlist[i].firstedges;
g->adjlist[i].firstedges=s;

结束

图2.5 createAgraph()函数流程图

5. 邻接矩阵Output()输出函数
开始
int i,j;
for (i=0;i<G->n;i++)
printf("%d ",G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
printf("\t%d ",G->edges[i][j]);
结束

图2.6 Output()函数流程图

3 数据结构分析
3.1 存储结构
定义邻接矩阵及邻接表的结构体
（1）邻接矩阵
#define MaxVertexNum 100
#define max 1000
typedef int VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vexs[MaxVertexNum];
EdgeType edges[MaxVertexNum][MaxVertexNum];
int n,e;
}MGraph;
（2）邻接表
#define MaxVertexNum 100
typedef int vertextype;
typedef struct node{
int adjvex;
int weight;
struct node *next;
}edgenode;
typedef struct vnode{
vertextype vertex;
edgenode *firstedges;
}vertexnode;
typedef vertexnode AdjList[MaxVertexNum];
typedef struct {
AdjList adjlist;
int n,e;
}ALgraph;
(3) 邻接表转换成邻接矩阵辅助结构体
typedef int edgetype ;
typedef struct
{
edgetype vexs[MaxVertexNum];
edgetype edges[MaxVertexNum][MaxVertexNum];
int n,e;
}graph; /*邻接表转换成邻接矩阵辅助结构体*/

3.2 算法描述
1. 创建有向网图邻接矩阵存储
void CreateMGraph(MGraph *G)
{
int i,j,k,weight;
printf("\t==有向网图邻接矩阵==\n");
printf("请输入顶点数和边数：");
scanf("%d,%d",&(G->n),&(G->e));
printf("请输入顶点信息:");
for (i=0;i<G->n;i++)
scanf("\n%d",&(G->vexs[i]));
for (i=0;i<G->n;i++)
for (j=0;j<G->n;j++)
{ if(i==j) G->edges[i][j]=0;
else G->edges[i][j]=max;
} /*初始化邻接矩阵*/
printf("输入边对应的两个顶点的序号及权值：");
for (k=0;k<G->e;k++)
{
scanf("\n%d,%d,%d",&i,&j,&weight);
G->edges[i][j]=weight;
}
printf("输出顶点信息及邻接矩阵:\n" );
OutPut(G);
printf("输出最小生成树的信息:\n");
prim(G->edges,G->n,G->vexs);
}
2. 创建无向网图邻接矩阵存储
void CreateGraph(MGraph *G)
{
int i,j,k,weight;
printf("\t==无向网图邻接矩阵==\n");
printf("请输入顶点数和边数：");
scanf("%d,%d",&(G->n),&(G->e));
printf("请输入顶点信息:");
for (i=0;i<G->n;i++)
scanf("\n%d",&(G->vexs[i]));
for (i=0;i<G->n;i++)
for (j=0;j<G->n;j++)
{ if(i==j) G->edges[i][j]=0;
else G->edges[i][j]=max;
} /*初始化邻接矩阵*/
printf("输入边对应的两个顶点的序号及权值：");
for (k=0;k<G->e;k++)
{ scanf("\n%d,%d,%d",&i,&j,&weight);
G->edges[i][j]=weight;
G->edges[j][i]=weight;
}
printf("输出顶点信息及邻接矩阵:\n" );
OutPut(G);
printf("输出最小生成树的信息:\n");
prim(G->edges,G->n,G->vexs);
}
3. 创建有向网图邻接表存储
void createAgraph( ALgraph *g) /*创建有向网图*/
{
int i,j,k,w;
edgenode *s;
printf("\t==有向网图邻接表==\n");
printf("输入顶点数和边数:");
scanf("%d,%d%*c",&(g->n),&(g->e));
printf("\n输入顶点:");
for(i=0;i<g->n;i++)
{scanf("%d",&(g->adjlist[i].vertex));
g->adjlist[i].firstedges=NULL;
}
printf("\n输入边和权值:");
for(k=0;k<g->e;k++)
{
scanf("%d,%d,%d",&i,&j,&w);
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=j;
s->weight=w;
s->next=g->adjlist[i].firstedges;
g->adjlist[i].firstedges=s;
}
DispAdjList(g);
}
4. 创建无向网图邻接表存储
void createALgraph(ALgraph *g) /*创建无向网图*/
{
int i,j,k,w;
edgenode *s;
printf("\t==无向网图邻接表==\n");
printf("输入顶点数和边数:");
scanf("%d,%d%*c",&(g->n),&(g->e));
printf("\n输入顶点:");
for(i=0;i<g->n;i++)
{scanf("%d",&(g->adjlist[i].vertex));
g->adjlist[i].firstedges=NULL;
}
printf("\n输入边和权值:");
for(k=0;k<g->e;k++)
{
scanf("%d,%d,%d",&i,&j,&w);
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=j;
s->weight=w;
s->next=g->adjlist[i].firstedges;
g->adjlist[i].firstedges=s;
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=i;
s->weight=w;
s->next=g->adjlist[j].firstedges;
g->adjlist[j].firstedges=s;

}
DispAdjList(g);
}
5.prim算法
void prim(int gm[][MaxVertexNum ],int n,int closevertex[] )
{ /*普里姆算法*/
int lowcost[100];
int mincost;
int i,j,k;
for(i=0;i<n;i++)
{
lowcost[i]=gm[0][i];
closevertex[i]=0;
}
lowcost[0]=0;
closevertex[0]=0;
for(i=1;i<n;i++)
{
mincost=max;
j=1;
k=1;

while(j<n)
{
if(lowcost[j]<mincost&&lowcost[j]!=0)
{
mincost=lowcost[j];
k=j;
}
j++;
}
printf("顶点的序号=%d 边的权值=%d\n",k,mincost);
lowcost[k]=0;
for(j=0;j<n;j++)
if(gm[k][j]<lowcost[j])
{
lowcost[j]=gm[k][j];
closevertex[j]=k;
}
}
}
6. 输出邻接矩阵存储函数
void OutPut (MGraph *G)
{
int i,j;
printf("\tE={ ");
for (i=0;i<G->n;i++)
printf("%d ",G->vexs[i]);
printf("}");
printf("\n");
for(i=0;i<G->n;i++)
{
for(j=0;j<G->n;j++)
printf("\t%d ",G->edges[i][j]);
printf("\n");
}
}
7. 输出邻接表存储函数
void DispAdjList(ALgraph *g)
{
int i;
edgenode *p;
printf("\n网图的邻接表表示如下：\n");
for (i=0; i<g->n; i++) {
printf("[%d,%3d]=>",i,g->adjlist[i].vertex);
p=g->adjlist[i].firstedges;
while (p!=NULL)
{
printf("(%d,%d)->",p->adjvex,p->weight);
p=p->next;
}
printf("^\n");
}
}
8. 邻接表转换成邻接矩阵函数
void change(ALgraph *g) /*邻接表转换成邻接矩阵*/
{
int i,j;
edgenode *p;
graph *M;
M=(graph*)malloc(sizeof(graph));
M->n=g->n;
M->e=g->e;
for(i=0;i<M->e;i++)
for(j=0;j<M->e;j++)
if(i==j)M->edges[i][j]=0;
else M->edges[i][j]=MaxVertexNum;
for(i=0;i<g->n;i++)
M->vexs[i]=g->adjlist[i].vertex;
for(i=0;i<g->n;i++)
{ p=g->adjlist[i].firstedges;
while(p)
{
M->edges[i][p->adjvex]=p->weight;
p=p->next;
}
}
prim(M->edges,M->n,M->vexs);
}

4 调试与分析
4.1 调试过程
测试数据（对下图进行测试）：
1

右图是6个顶点的10条边的连通图
六个顶点分别是：
1 2 3 4 5 6
顶点序号和边上的权植分别是
0 1 11
0 2 15
0 3 18
1 2 33
1 4 12
2 3 20
2 4 22
2 5 25
3 5 27
4 5 29

4
2

3

6
5

4.2程序执行过程
系统使用说明：
1. 输入的数据可以是100以内的整数；
2. 本系统可以建立带权图，并能够用Prim算法求该网图的最小生成树。
3. 该系统会有菜单提示，进行选项：

4.程序实际运行截图
（1）有向图邻接矩阵输出最小生成树截图：

（2）无向图邻接矩阵输出最小生成树截图：

（3） 有向图邻接表输出最小生成树截图：

（4） 无向图邻接表输出最小生成树截图：

参考文献
（1）李素若，《数据结构（C语言描述）》，2009，化学工业出版社
（2）严蔚敏、吴伟民，《数据结构（C语言描述）》，1999，清华大学出版社
（3）徐孝凯，数据结构课程实验，2002，清华大学出版社
（4）孟佳娜、胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社

附 录
说明：
本次课程设计由组长周鑫，组员王彬彬、李松平、张圣玮、魏远迎共同完成。其中邻接矩阵存储有向图、无向图及调用普里姆算法生成最小生成树、流程图绘制、任务书填写由王彬彬完成；邻接表存储有向图、无向图及调用普里姆算法生成最小生成树、菜单界面由周鑫完成；李松平、张圣玮、魏远迎主要负责文档排版，代码调试等综合应用。

课程设计总结：
本次课程设计涉及到的范围虽不广，但能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。
1. 巩固了以前学过的C语言的知识，在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用VC++的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用
2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。
3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法。
4. 此次课程设计时间虽短，课设的过程是短暂的，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远的影响。
指导教师评语：

指导教师(签字)：　　　　　　 年 月 日

课程设计成绩