数据结构课程设计-- 图的遍历和生成树求解.docVIP

图的遍历和生成树求解摘要：图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。图的最小生成树基于图的两种存储结构，采用Prim算法和Kruskal算法对图的最小生成树进行求解。关键词：图；存储结构；遍历 ；最小生成树目 录1.设计背景11.1课程设计目的11.2题目要求12.设计方案12.1设计方法12.2方法实现23. 方案实施33.1采用的数据结构说明及类型的定义33.2函数功能描述及相关函数的实现53.3程序中需说明的地方，如用到的宏及代表的意义164. 结果与结论 174.1测试数据及测试结果174.2实验结论195.收获与致谢196.参考文献20图的遍历和生成树求解1. 设计背景1.1课程设计目的通过本课程设计，加深对面向对象程序设计C+课程所学知识的理解，熟练掌握和巩固C+语言的基本知识和语法规范,掌握使用面向对象程序设计语言C+，或面向对象开发平台Visual C+等,培养调查研究、查阅技术文献、资料、手册以及编写技术文献的能力。学会编制结构清晰、风格良好的C+语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。1.2题目要求课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程. 通过课程设计，巩固和加深对队列以及图等理论知识的理解；掌握现实复杂问题的分析建模和解决方法，掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人动手能力，历练自身素质。2.设计方案2.1设计方法2.1.1问题的分析和结构的设计思路1） 图的遍历和生成树求解所有功能：图的生成、图的遍历、最小生成树求解。2） 需要创建所有图的存储结构(邻接矩阵存储结构和邻接表存储结构)。3）程序设计的目的是通过屏幕上输出的提示语句，进行相应的操作。4）选择适当的算法，实现图的遍历和最小生成树的求解等功能。5）选择适当的变量，来表示图相应的顶点、边、边的权值等信息。6）当输入的信息出错时，程序应给错误信息提示，使程序设计得全面周密。2.1.2图的遍历和生成树求解的算法思想及设计1） 由于图的存储结构不同，故采用邻接矩阵和邻接表两种存储结构建立图。 2）对图的深度遍历基于邻接矩阵，广度遍历基于邻接表。3）基于邻接矩阵存储结构，用prim算法求图的最小生成树。 4）基于邻接表存储结构，用Kruskal算法求图的最小生成树。5）综合1、2、3三点因素，可以采用队列来实现对图的广度优先遍历的算法，其示意图如下：Q.frontnext其中：1. Q.front为队头指针,Q.rear为队尾指针2. data域存图的边权值和顶点位序等相关信息。3. next域指向与改结点同类型的下一个结点nextdatadatanextQ.rear 6）图遍历和生成树求解的总体结构框图如下：图的遍历和生成树的求解建立邻接矩阵输出邻接矩阵BFS遍历建立邻接表输出邻接表DFS遍历Prim求最小生成树Kruskal求最小生成树2.2方法实现2.2.1创建结点1）建立队列LinkQueue，以及队头指针front、队尾指针rear。2)建立图的存储类型MGraph,以及顶点向量vexs。3)建立图的邻接矩阵AdjMatrix，以及边的权值。4)建立图的邻接表ALGraph,以及邻接表头结点的类型AdjList，弧的结点结构类型ArcNode。2.2.2编写函数建立具体的功能实现函数，如初始化、录入、输出等。1.基于邻接矩阵创建图CreateUDN(MGraph &G,AdjMatrix &GA)2.基于邻接表建立图CreateALGraph(ALGraph &G) 3.邻接矩阵的输出Display(MGraph G,AdjMatrix GA)4.邻接表的输出DisplayG(ALGraph G) 5.基于邻接矩阵图进行深度优先遍历DFS1(MGraph G,int n,int v)6.对结点队列初始化InitQueue (LinkQueue &Q) 7.判断队列是否为空 QueueEmpty (LinkQueue Q)8.顶点信息入队EnQueue (LinkQueue &Q,int e)9.顶点信息出队DeQueue (LinkQueue &Q,int &e)10.基于邻接表对图进行广度优先遍历BFS(ALGraph G,int v)11.Prim求生成树MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u) 12.Kruskal求生成树Kruskal(ALGraph G)13. 求顶点在图中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)14.主函数main()3.方案实施3.1 采用的数据结构说明及类型的定义1邻接矩阵的存储表示如下typedef struct ArcCellVRType adj; /VRType是顶点关系类型，对无权图，用0和1；对有权图，则为权值类型 InfoType *info; /该弧相关信息的指针(可无)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind;/图的种类标志MGraph;2邻接表的存储表示如下typedef struct ArcNode /弧的结点结构类型int adjvex;/该弧所指向的顶点的位置 int weight;/*该弧的权重*/struct ArcNode *nextarc;/指向下一条弧的指针InfoType *info;/该弧相关信息的指针(可无)ArcNode;typedef struct VNode/邻接表头结点的类型vertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct/邻接表AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数ALGraph3队列的存储结构typedef struct QNode TElemType data; QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针LinkQueue;4Prim算法辅助数组存储结构typedef struct /辅助数组存储结构 VertexType adjvex;VRType lowcost;Closedge MAX_VERTEX_NUM;3.2函数功能描述及相关函数的实现1.基于邻接矩阵创建图CreateUDN(MGraph &G,AdjMatrix &GA)Status CreateUDN(MGraph &G,AdjMatrix &GA)/用邻接矩阵表示法，构造无向网G，以及表示出其邻接矩阵GAint i,j,k,w;VertexType v1,v2;printf(请输入无向网G的顶点数,边数:n);scanf(%d,%d,&G.vexnum,&G.arcnum,);printf(请输入%d个顶点的值:n,G.vexnum); for(i=1;i=G.vexnum;+i) scanf(%s,&G.vexsi); /构造顶点向量getchar();for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+) /初始化邻接矩阵GAij.adj=INFINITY;GA=NULL;printf(请输入%d条边的顶点1顶点2和权值(以空格作为间隔):n,G.arcnum);for(k=1;k=G.arcnum;k+)scanf(%s%s%d,&v1,&v2,&w); /输入一条边依附的顶点和权值i=LocateVex(G,v1);j=LocateVex(G,v2); /确定v1和v2在G中的位置GAij.adj=GAji.adj=w; /弧的权值 和的对称弧return OK;2.基于邻接表建立图CreateALGraph(ALGraph &G) Status CreateALGraph(ALGraph &G) /用邻接表表示法，构建无向网Gint i,j,k,w; ArcNode *s,*p; printf(请输入顶点数和边数(输入格式为:顶点数,边数)：n); scanf(%d,%d,&(G.vexnum),&(G.arcnum); vertexType v1,v2; printf(请输入顶点信息：n); for ( i=1;i=G.vexnum;i+) scanf(n%c,&(G.verticesi.data); /初始化邻接表的头结点 G.verticesi.firstarc=NULL; printf(请输入边的信息(输入格式为:v1,v2,w)：n); for (k=1;kadjvex=j; s-weight=w; s-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=s;/将下标为j的结点连接在下标为i的结点后面 p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=i; p-weight=w; p-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=p; /将下标为i的结点连接在下标为j的结点后面 return OK; 3.邻接矩阵的输出Display(MGraph G,AdjMatrix GA)void Display(MGraph G,AdjMatrix GA) /邻接矩阵的输出int i,j;for(i=1;i=G.vexnum;i+) printf(G.vexs%d=%cn,i,G.vexsi); /输出顶点向量printf(邻接矩阵GA.adj:n); for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)printf(%5d,GAij.adj);printf(n); 4.邻接表的输出DisplayG(ALGraph G) void DisplayG(ALGraph G) /邻接表的输出int i;ArcNode *p;for(i=1; i ,i,G.verticesi.data); while(p) if(p-nextarc) printf(%d,%c,%d-,p-adjvex,G.verticesp-adjvex.data,p-weight); else printf(%d,%c,%d-/,p-adjvex,G.verticesp-adjvex.data,p-weight); p=p-nextarc; printf(n);5.基于邻接矩阵图进行深度优先遍历DFS1(MGraph G,int n,int v)int visitedMAX_VERTEX_NUM; /初始化标志数组Status DFS1(MGraph G,int n,int v)/基于邻接矩阵，对图G进行深度优先搜索int j;AdjMatrix A;printf(%3d,v);printf(%c,G.vexsv);visitedv=1;for(j=1;jnext=NULL;return OK;7.判断队列是否为空 QueueEmpty (LinkQueue Q)int QueueEmpty (LinkQueue Q)/判断队列是否为空 if(Q.front=Q.rear) return 1; return 0;8.顶点信息入队EnQueue (LinkQueue &Q,int e)Status EnQueue (LinkQueue &Q,int e)/结点进队 QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;9.顶点信息出队DeQueue (LinkQueue &Q,int &e)int DeQueue (LinkQueue &Q,int &e)/结点出队 if(Q.front=Q.rear) printf(队列为空！n); QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;10.基于邻接表对图进行广度优先遍历BFS(ALGraph G,int v)int visited1MAX_VERTEX_NUM;/初始化标志数组Status BFS(ALGraph G,int v)/基于邻接表，对无向图G进行广度优先搜索 int u, w; LinkQueue Q; InitQueue(Q); if(!visited1v) visited1v=1; printf(%ct,G.verticesv.data); EnQueue(Q,v); while(!QueueEmpty(Q) DeQueue(Q,u); for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w) if(!visited1w) visited1w=1; printf(%ct,G.verticesw.data); EnQueue(Q,w); return OK;11.Prim求生成树MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u) Status MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u)/用Prim算法从第u个顶点出发构造网G的最小生成树T，输出T的各边 int k,j,i; Closedge closedge; k=LocateVex(G,u);for(j=1;j=G.vexnum;j+)if(j!=k) closedgej.adjvex=u; closedgej.lowcost=GAkj.adj;/ 辅助数组初始化closedgej.adjvex = 0;closedgej.lowcost = 88;closedgek.adjvex = u;closedgek.lowcost=0;/初始U=uprintf(最小生成树的各条边为:n);for(i=2;i=G.vexnum;+i)/选择其余的G.vexnum-1个顶点k=minimum(closedge); /求出T的下一个结点；第k个顶点printf(%c-%cn,closedgek.adjvex,G.vexsk);/输出生成树的边closedgek.lowcost=0;/第k顶点并入U集for(j=1;j=G.vexnum;+j)if(GAkj.adjclosedgej.lowcost)/新顶点并入U集后，重新选择最小边closedgej.adjvex=G.vexsk; closedgej.lowcost=GAkj.adj;return OK;12.Kruskal求生成树Kruskal(ALGraph G)Status Kruskal(ALGraph G)int i,j,min = INFINITY,k = 1;/min用于记录最小权值，k表示当前构造的第几条边int setMAX_VERTEX_NUM;/用于判断两个点是否在同一集合里ArcNode *p,*q,*s;for(i = 1; i = G.vexnum; +i) seti = i;/初始化，将每个点自身作为一个集合 while(kG.vexnum&k=G.arcnum )for(i = 1; i nextarc)/查找最小权值的边if(p-weight weight;q = p;j = i;if(G.verticesj.firstarc = q) G.verticesj.firstarc = q-nextarc; /if-else用于删除最小权值的边elsefor(p = G.verticesj.firstarc; p != q; p = p-nextarc) s = p;s-nextarc = q-nextarc;if(setj!=setq-adjvex)/判断两点是否在同一集合,若不在，则输出这条边printf(%c,%c) %dn,G.verticesj.data,G.verticesq-adjvex.data,q-weight);k+;/*int s2=setj;*/for(i=1;iadjvex;min = INFINITY; /将min置为最大值return OK;13.求顶点在图中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)Status LocateVex(MGraph G,VertexType u) int i;for(i=1;i=G.vexnum;+i)if(G.vexsi=u)return i;return -1;Status LocateVexG(ALGraph G,vertexType e) for(int i=1;i=G.vexnum;i+) if(G.verticesi.data=e) return i; return -1;14.主函数main()int main() ALGraph A;MGraph G;AdjMatrix S;int n,v; VertexType u;printf(用图的邻接矩阵存储结构建无向网:n); CreateUDN(G,S);printf(输出邻接矩阵：n);Display(G,S);printf(用图的邻接表存储结构建无向网：n); CreateALGraph(A); printf(输出邻接表：n); DisplayG(A);printf(n); printf(输入图的结点个数以及访问的起始结点的位序(格式如：2,1)：n); scanf(%d,%d,&n,&v); printf(对图进行深度优先遍历（邻接矩阵）：n); DFS1(G,n,v);printf(n); printf(对图进行深度优先遍历（邻接表）：n);DFS2(A,v); printf(n); printf(对图进行广度优先遍历（邻接表）：n); BFS(A,v);printf(n);printf(利用PRIM算法求最小生成树n);u=G.vexs1; MiniSpanTree_PRIM(G,S,u);printf(利用Kruskal算法求最小生成树n); Kruskal(A);printf(n); return OK;3.3 程序中需说明的地方，如用到的宏及代表的意义#define OK 1#define ERROR 0#define INFINITY 88 /最大值（表示无穷大）#define MAX_VERTEX_NUM 20 /最大顶点个数#define MAX_INFO 20#define MAX_NAME 5typedef int Status; typedef char VertexType;typedef int VRType;typedef char vertexType;typedef char InfoType;typedef enumDG,DN,UDG,UDNGraphKind; /有向图,有向网,无向图,无向网typedef int TElemType;4. 结果与结论4.1测试数据及测试结果1.程序运行开始界面：2.测试录入顶点信息以及边的信息，录入数据及录入结果如下：3.测试输出邻接矩阵的函数4测试基于邻接表构造图函数5. 测试输出邻接表的函数6. 测试基于邻接矩阵对图进行深度优先遍历的函数7.测试基于邻接表对图进行广度优先遍历的函数8.测试Prim算法求最小生成树的函数9