普里姆算法生成最小生成树_课程设计

JINGCHU UNIVERSITY OF TECHNOLOGY

《数据结构（C语言描述）》

课程设计

学 院 运算机工程学院 班 级 12级软件技术1班 学 号 20、120

124、133、121

学生姓名 周鑫、王彬彬、李松平 张圣玮、魏远迎 指导教师 余云霞

2014年 1月3日

目 录

1 课程设计介绍 ..................................... 错误!未定义书签。

课程设计内容 ....................................... 错误!未定义书签。 课程设计要求 .............................................................................. 错误!未定义书签。

2 课程设计原理 ............................................................................. 错误!未定义书签。

课设题目粗略分析 ...................................................................... 错误!未定义书签。 原理图介绍 .................................................................................. 错误!未定义书签。

功能模块图 .............................................................................. 错误!未定义书签。

流程图分析 .............................................................................. 错误!未定义书签。 3 数据结构分析 ............................................................................. 错误!未定义书签。

存储结构 ...................................................................................... 错误!未定义书签。 算法描述 ...................................................................................... 错误!未定义书签。

4 调试与分析 .............................................................................................................. 22

调试进程 ................................................................................................................... 22

程序执行进程 ..................................................................................................... 22

参考文献 ........................................................................................................................ 28 附 录 .......................................................................................................................... 28

1 课程设计介绍

课程设计内容

编写算法能够成立带权图，并能够用Prim算法求该图的最小

生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采纳极点集合和边的集合的形式。

课程设计要求

1. 能够输入极点、边数及各途径的权值；

2. 通过成立无向图或有向图能过输出邻接矩阵或邻接表； 3. 能够输出成立的最小生成树；

4. 画出流程图，且函数有必要说明、注释； 5. 课设完成后上交报告及核心代码。

2 课程设计原理

课设题目粗略分析

依照课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：

1. 创建网图并确信网图的存储形式，通过对题目要求的具体分析。发觉该题的要紧操作是途径的输出，因此采纳邻接表和邻接矩阵（起点、终点和权值）两种存储结构，方便以后的编程。

算法。设置两个新的集合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时，最小生成树便构造完毕。

原理图介绍

功能模块图

开始 显示菜单进行选择 选择创建（有）无向图及存储方式 有向图邻接矩阵 无向图邻接矩阵 有向图邻接表 无向图邻接表 调用普里姆算法输出最小生成树 结束 图 功能模块图

流程图分析

1. 主函数

开始 显示菜单，选择输入1或2 选择1 选择2 选择1 选择2 调用CreateMGraph()函数 调用createAgraph()函数 调用CreateGraph()函数 调用createALgraph()函数 调用Prim函数，输出最小生成树 结束

图 主函数流程图

2. CreateMGraph()函数

开始 int i,j,k for(i=0;in;i++) scanf(“\\n%c”,&(G->vexs[i])); for(i=0;in;i++) for(j=0;in;i++) Y N i=j G->edges[i][j]=0; G->edges[i][j]=max; for (k=0;ke;k++) scanf(\"\\n%d,%d,%d\G->edges[i][j]=weight; OutPut(G); prim(G->edges,G->n,G->vexs);

结束

图 CreateMGraph()函数流程图

3．Prim()函数

开始 int i,j,k,lowcost[100],mincost; for(i=1;ifor(j=0;j图 Prim()函数流程图

4. createALgraph()函数

开始 int i,j,k,w; edgenode *s; scanf(\"%d,%d%*c\for(i=0;in;i++) scanf(\"%d\g->adjlist[i].firstedges=NULL; for(k=0;ke;k++) scanf(\"%d,%d,%d\s=(edgenode*)malloc(sizeof(edgenode)); s->adjvex=j; s->weight=w; s->next=g->adjlist[i].firstedges; g->adjlist[i].firstedges=s; 结束 图 createAgraph()函数流程图

5. 邻接矩阵Output()输出函数

开始 int i,j; for (i=0;in;i++) printf(\"%d \for(i=0;in;i++) for(j=0;jn;j++) printf(\"\%d \结束 图 Output()函数流程图

3 数据结构分析

存储结构

概念邻接矩阵及邻接表的结构体

（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; /*邻接表转换成邻接矩阵辅助结构体*/

算法描述

1. 创建有向网图邻接矩阵存储 void CreateMGraph(MGraph *G) {

int i,j,k,weight;

printf(\"\==有向网图邻接矩阵==\\n\"); printf(\"请输入极点数和边数：\"); scanf(\"%d,%d\ printf(\"请输入极点信息:\"); for (i=0;in;i++)

scanf(\"\\n%d\ for (i=0;in;i++) for (j=0;jn;j++)

{ if(i==j) G->edges[i][j]=0;

else G->edges[i][j]=max;

} /*初始化邻接矩阵*/

printf(\"输入边对应的两个极点的序号及权值：\"); for (k=0;ke;k++) {

scanf(\"\\n%d,%d,%d\ 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(\"\==无向网图邻接矩阵==\\n\"); printf(\"请输入极点数和边数：\"); scanf(\"%d,%d\ printf(\"请输入极点信息:\"); for (i=0;in;i++)

scanf(\"\\n%d\ for (i=0;in;i++) for (j=0;jn;j++)

{ if(i==j) G->edges[i][j]=0;

else G->edges[i][j]=max;

} /*初始化邻接矩阵*/

printf(\"输入边对应的两个极点的序号及权值：\"); for (k=0;ke;k++)

{ scanf(\"\\n%d,%d,%d\ 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(\"\==有向网图邻接表==\\n\"); printf(\"输入极点数和边数:\"); scanf(\"%d,%d%*c\ printf(\"\\n输入极点:\"); for(i=0;in;i++)

{scanf(\"%d\ g->adjlist[i].firstedges=NULL; }

printf(\"\\n输入边和权值:\"); for(k=0;ke;k++) {

scanf(\"%d,%d,%d\ 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(\"\==无向网图邻接表==\\n\");

printf(\"输入极点数和边数:\"); scanf(\"%d,%d%*c\ printf(\"\\n输入极点:\"); for(i=0;in;i++)

{scanf(\"%d\ g->adjlist[i].firstedges=NULL; }

printf(\"\\n输入边和权值:\"); for(k=0;ke;k++) {

scanf(\"%d,%d,%d\ 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); } 算法

void prim(int gm[][MaxVertexNum ],int n,int closevertex[] )

{ /*普里姆算法*/ int lowcost[100]; int mincost; int i,j,k; for(i=0;ilowcost[i]=gm[0][i]; closevertex[i]=0; }

lowcost[0]=0; closevertex[0]=0; for(i=1;imincost=max; j=1;

k=1;

while(jif(lowcost[j]mincost=lowcost[j]; k=j; } j++; }

printf(\"极点的序号=%d 边的权值=%d\\n\ lowcost[k]=0; for(j=0;jif(gm[k][j]lowcost[j]=gm[k][j]; closevertex[j]=k; } } }

6. 输出邻接矩阵存储函数

void OutPut (MGraph *G) { int i,j;

printf(\"\E={ \");

for (i=0;in;i++) printf(\"%d \ printf(\ printf(\"\\n\"); for(i=0;in;i++) {

for(j=0;jn;j++) printf(\"\%d \ printf(\"\\n\"); } }

7.输出邻接表存储函数 void DispAdjList(ALgraph *g) { int i; edgenode *p;

printf(\"\\n网图的邻接表表示如下：\\n\"); for (i=0; in; i++) {

printf(\"[%d,%3d]=>\ p=g->adjlist[i].firstedges; while (p!=NULL) {

printf(\"(%d,%d)->\ 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;ie;i++) for(j=0;je;j++) if(i==j)M->edges[i][j]=0;

else M->edges[i][j]=MaxVertexNum; for(i=0;in;i++)

M->vexs[i]=g->adjlist[i].vertex; for(i=0;in;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 调试与分析

调试进程

测试数据（对以下图进行测试）：

右图是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 5 29 4 1 2 4 3 5 6 程序执行进程

系统利用说明：

1. 输入的数据能够是100之内的整数；

2. 本系统能够成立带权图，并能够用Prim算法求该网图的最小生成树。

3. 该系统会有菜单提示，进行选项：

4.程序实际运行截图

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

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

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

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

参考文献

（1）李素假设，《数据结构（C语言描述）》，2020，化学工业出版社 （2）严蔚敏、吴伟民，《数据结构（C语言描述）》，1999，清华大学出版社

（3）徐孝凯，数据结构课程实验，2002，清华大学出版社

（4）孟佳娜、胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社

附 录

说明：

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

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