图的创建及最小生成树.doc

《图的创建及最小生成树.doc》由会员分享，可在线阅读，更多相关《图的创建及最小生成树.doc（26页珍藏版）》请在三一文库上搜索。

1、数据结构课程设计报告 南京工程学院课程设计说明书(论文)题 目 图的创建及最小生成树_ _ 课 程 名 称 _ 数据结构 _ 院（系、部、中心） 通信工程学院 专 业 通信工程（计算机通信） 班 级 学 生 姓 名 学 号 设 计 地 点 指 导 教 师 设计起止时间：2011年1月04日至2011年1月07日 目录1. 功能描述12. 总体设计12.1数据结构描述与定义12.2模块设计23. 测试结果与分析83.1测试一83.2测试二114. 课程设计总结14参考文献14附录151功能描述采用文件存储无向网的结点信息，然后分别运用邻接矩阵和邻接表的形式将无向网描述出来；在上述基础上，实现图的

2、遍历（在邻接表结构中实现图的度的计算和DFS遍历；在邻接矩阵结构中将各结点信息输出以实现遍历）。最后，求出此图的最小生成树，输出边信息。2总体设计21数据结构描述与定义所用的到的主要数据结构。#define MAX_VERTEX_NUM 20 /最大顶点个数为20#define MAX 1000 /代替无穷大的数int visitedMAX_VERTEX_NUM;/*邻接矩阵定义*typedef struct ArcCell int adj;/权值类型char *info;/该弧相关信息的指针ArcCell, ADjMatrixMaxVerNumMaxVerNum;typedef struct

3、 char vexsMaxVerNum;ADjMatrix arcs;int vexnum,arcnum;MGraph; /*邻接表定义* typedef struct ArcNode int adjvex; int info;struct ArcNode * nextarc; ArcNode;/表结点typedef struct VNode char data; ArcNode * firstarc; VNode, AdjListMAX_VERTEX_NUM;/头结点typedef structAdjList vertices; /邻接表int vexnum,arcnum; /顶点数和弧数A

4、LGraph; /*辅助数组定义*typedef struct ArcInfo char adjvex; int lowcost;ArcInfo, MinEdgeMAX_VERTEX_NUM;/PRIM最小边辅助数组22模块设计主程序及主要模块流程图： 主函数采用菜单的方式进行图的操作。采用do循环的方式输出菜单，其中设置有四个模块：1.邻接表方式创建无向网；2.邻接矩阵方式创建图；3.DFS遍历；4.PRIM最小生成树；5.退出，五种操作。开始结束菜单输入操作类型zz=1z=2z=4z=3CreateALGraph()PRIM()CreateMGraph()Exit()DFSM()z=01.

5、邻接矩阵的创建从文件中读入要创建的无向网的顶点个数和边的个数，然后循环读入各边的信息（包括依附的两个顶点和权值），并用一个二维数组存储起来。结束开始初始化 数组G.arcsij.adj=Maxi=0 j=0iG.arcnum从文件读入G.arcsij.adj=wG.arcsji.adj =G.arcsij.adjYi+N2.邻接表的创建从文件中读入要创建的无向图的顶点个数和边的个数，以结节点类型创建长度为结点个数的数组。采用循环读入边的信息，根据每次读入的信息，选择表结点依附的头结点位置，链接起来。并做出对称结点的链接。从而构成整个无向图的邻接表。结束开始i=0iG.vexnum初始化G.ve

6、rticesii+YNk=0iadjvex=i s-nextarc=G.verticesj.firstarcG.verticesj.firstarc=sN3.DFS遍历用访问标志数组visited存储访问与否信息。循环从结点开始访问相邻结点，若已访问visited置1。开始初始化visit=0v=0vG.vexnum!visitv访问结点vvisitv=1v+结束YYNN4.PRIM最小生成树设置一辅助数组closedge，记录从U到V-U具有最小代价边的信息。它包括两个域，其中lowcost存储该边上的权值，vex域存储该边依附的U中的点。（将U中元素的lowcost置0，以区分其余顶点）。

7、从u1开始树的创建，U=u1,将closedge初始化，存入u1与其他顶点间的边信息,在这些边信息中找到最小代价边输出。然后将u2并入U，成为U=u1,u2。再将u2与V-U各点的边信息与closedge中存储的进行比较，然后保留较小的，得到U到V-U各点权值较小边的信息数组closedge。采用循环重复上述操作，直到U中包含所有顶点。k=uj=0jG.vexnum开始closedgej-u,G.arcskj.adjj+Yclosedgek-u,0i=1jG.vexnumk=min(closedge)输出边closek.adj=G.vexskclosedgek=0j=0jG.vexnumGkj

8、.adjclosej.lowcostclosedgej-G.vexsk,G.arcskj.adjj+i+结束YYYNNN3测试结果与分析3.1测试结点为6，边为10的无向网（如图1）CABEDF555626453图1 测试一 网的模型（六个顶点，十条边）11.邻接矩阵方式创建无向网 测试文件1.TXT: 6,10 0,1,6 0,2,1 0,3,5 1,2,5 1,4,3 2,3,5 2,4,6 2,5,4 3,5,2 4,5,6测试结果：2.邻接表方式创建无向网 测试文件2.TXT: 6,10 0,1 0,2 0,3 1,2 1,4 2,3 2,4 2,5 3,5 4,5测试结果：3.DFS

9、遍历 测试结果：4.PRIM最小生成树ABEDFC354231图1.1 PRIM最小生成树测试结果：3.2测试二.测试结点为7，边为12的无向网（如图2）ABCDFEG图2 测试二 网的模型（七个顶点，十二条边）3142541332211.邻接矩阵方式创建无向网 测试文件1.TXT:7,12 0,1,1 0,2,3 0,3,2 1,3,5 1,4,4 2,3,4 2,5,1 3,4,2 3,5,3 3,6,2 4,6,1 5,6,3测试结果：2.邻接表方式创建无向网 测试文件2.TXT:7,12 0,1 0,2 0,3 1,3 1,4 2,3 2,5 3,4 3,5 3,6 4,6 5,6测试

10、结果：3.DFS遍历 测试结果：4.PRIM最小生成树ABCDFEG212131图2.1 PRIM最小生成树3.3测试结果分析： 测试中生成树的路径只有一种，无论从哪个顶点开始最小生成树的创建，都不会有相同权值的边纠缠。即便如此，无论你从哪个节点开始最小生成树的创建，结果也是唯一的。说明算法是成功的。4课程设计总结经过为期一周的课程设计，使我对数据结构有了更进一步的认识和了解。这一周一直忙于程序的编写，反复地修改，反复地调试，最后终于做出了让我比较满意的程序。通过上机让我意识到很多的不足。首先是打字，指法不对，经常按错字母，通过一周的练习有所改进。还有就是基础知识掌握不牢，一些简单的程序都需要

11、查资料，通过实践才记住。通过课程设计的学习，收获颇丰，我认识到学好计算机语言的重要性，不仅仅是数据结构，其他的方面的知识都要重在实践。所以在以后的学习中，一定会加强实践。参考文献:1严蔚敏，吴伟民数据结构（C语言版）北京：清华大学出版社，19972朱战立 数据结构西安：西安电子科技大学出版社,20043严蔚敏，吴伟民 数据结构题集（C语言版）北京：清华大学出版社,20004廖雷，袁璟，陈立C语言程序设计基础北京：高等教育出版社，2004附录：源程序：#include#include#define MAX_VERTEX_NUM 20 /最大顶点个数为20#define MAX 100 /代替无穷

12、大的数int visitedMAX_VERTEX_NUM;/*邻接矩阵定义*typedef struct ArcCell int adj; char *info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM;AdjMatrix arcs; int vexnum,arcnum; MGraph;/*邻接表定义*typedef struct ArcNode /表结点 int adjvex; struct ArcNode *nextarc; ArcNode;typedef st

13、ruct VNode /头结点char data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef structAdjList vertices; int vexnum,arcnum; ALGraph;/*辅助数组定义*typedef struct ArcInfo /PRIM最小边辅助数组char adjvex;int lowcost;ArcInfo,MinEdgeMAX_VERTEX_NUM;/*图的存储及遍历（邻接矩阵）*int CreateMGraph(MGraph &G) int i,j,k;char filename10

14、;int a,b; /用来存储边依附的点v1,v2的位置int w;FILE *fp1;printf(t请输入文件名称：nt);scanf(%s,filename);if(fp1=fopen(filename,r)=NULL)printf(t文件打开失败！);return 0;fscanf(fp1,%d,%d,&G.vexnum,&G.arcnum);printf(t已创建的邻接表的结点跟弧的个数：n);printf(t%5d%5dn,G.vexnum,G.arcnum);for(i=0;iG.vexnum;+i) G.vexsi=A+i;for(i=0;iG.vexnum;+i) for(j

15、=0;jG.vexnum;+j)G.arcsij.adj=MAX; for(k=0;kG.arcnum;+k) fscanf(fp1,%d,%d,%d,&a,&b,&w); G.arcsab.adj=w; G.arcsba=G.arcsab; return 1;void PrintMG(MGraph G) /输出无向图int i,j;printf(t输出无向图的结果为： n);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(!j)printf(t);if(G.arcsij.adj!=100)printf(%5d,G.arcsij.adj);elsepr

16、intf( );printf(n);printf(n);/*图的存储及遍历（邻接表）*int CreateALGraph(ALGraph &G) int i,j,k;ArcNode *s;char filename10;FILE *fp2;printf(t请输入文件名称：nt);scanf(%s,filename);if(fp2=fopen(filename,r)=NULL)printf(t文件打开失败！);return 0;fscanf(fp2,%d,%d,&G.vexnum,&G.arcnum); printf(t创建的无向图的结点数和边数分别为：n);printf(t%5d%5dn,G.

17、vexnum,G.arcnum);for(i=0;iG.vexnum;i+)G.verticesi.data=A+i;G.verticesi.firstarc=NULL;for(k=0;kadjvex=j; s-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=s;s=(ArcNode *)malloc(sizeof(ArcNode); s-adjvex=i; s-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=s; return 1;/*求出度*void VertOD(ALGraph G

18、)int i,OD;ArcNode *p;printf( nt图中结点的度：);for(i=0;inextarc;printf(nt结点%d的度为：%d,i,OD);printf(nn);/*图的遍历*void DFS(ALGraph G,int v) ArcNode *p;visitedv=1; printf(%c ,G.verticesv.data); for (p=G.verticesv.firstarc;p;p=p-nextarc)if (!visitedp-adjvex) DFS(G,p-adjvex);void DFSAL(ALGraph G) /全部遍历int v;for(v=0

19、;vG.vexnum;v+) /初始化 visitedv=0; printf(t遍历结果为：);for(v=0;vG.vexnum;v+) if (!visitedv)DFS(G,v);printf(n);/*FRIM*void PRIM(MGraph G,int u) int i,j;int k,temp;MinEdge closedge;k=u; for(j=0;jG.vexnum;j+) /辅助数组初始化if(j!=k)closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj;/adjvex,lowcostclosedgek.low

20、cost=0; /初始，U=uclosedgek.adjvex=G.vexsk;printf(n);printf(t最小生成树的各边为：n);for(i=1;iG.vexnum;i+) /选择其余G.vexnum-1个顶点temp=MAX;for(j=0;jclosedgej.lowcost&closedgej.lowcost!=0)k=j;temp=closedgej.lowcost; /求出T的下一个结点：第k顶点printf(t%c,%cn,closedgek.adjvex,G.vexsk);closedgek.lowcost=0; /第k顶点并入U集for(j=0;jG.vexnum;

21、j+)if(G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;void main()int u,flag;ALGraph AG;MGraph MG;int PushButton;char ch;dosystem(cls);printf(*);printf(*菜 单*n);printf(* 1、 显示该图的邻接矩阵 *n);printf(* 2、 显示该图的邻接表 *n);printf(* 3、 深度优先遍历 *n);printf(* 4、 最小生成树PRIM算法 *n);p

22、rintf(* 0、 退出 *n);printf(*);printf(*n);printf(t请按04按键进行操作：);scanf(%d,&PushButton);switch(PushButton) case 1:flag=CreateMGraph(MG); if(!flag)return;PrintMG(MG);ch=getchar();ch=getchar();break; case 2:flag=CreateALGraph(AG); if(!flag)return;VertOD(AG);ch=getchar();ch=getchar();break; case 3:DFSAL(AG);ch=getchar();ch=getchar();break; case 4:printf(n);printf(t请输入最小生成树的起始位置);scanf(%d,&u);PRIM(MG,u);ch=getchar();ch=getchar();break; case 0:printf(nt退出);break;default:printf(nt非法操作!n);while(PushButton!=0);- 24 -