数据结构课程设计-图的遍历和生成树求解问题的研究与实现.doc

此文档收集于网络，如有侵权，请联系网站删除数据结构课程设计设计说明书图的遍历和生成树求解问题的研究与实现学生姓名学号班级信管061成绩指导教师计算机科学与技术系2008年3月8日精品文档数据结构 课程设计评阅书题目图的遍历和生成树求解问题的研究与实现学生姓名秦洁学号0621024014指导教师评语及成绩指导教师签名： 年 月 日答辩评语及成绩 答辩教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日课程设计任务书20072008学年第一学期专业： 信息管理与信息系统 学号： 0621024014 姓名： 秦洁 课程设计名称： 数据结构课程设计 设计题目： 图的遍历和生成树求解问题的研究与实现 完成期限：自 2008 年 2 月 25 日至 2008 年 3 月 7 日共 2 周设计依据、要求及主要内容（可另加附页）：设计依据：数据结构算法设计要求：先任意创建一个图；图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。主要内容：对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储，并完成图的DFS和BFS操作。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要图是一种较线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词： 图；存储；遍历；深度；广度 目 录1 课题描述12 设计过程2 2.1 设计思路22.2 设计流程图32.3 程序源代码43 编译运行 17总结 19参考文献 201 课题描述图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子节点）相关，但只能和上一层中一个元素（即其双亲节点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。开发工具：Visual C+6.02设计过程 本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.1 设计思路这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.2 设计流程图开始创建图G用邻接表存储图If y=yNY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母If y=y结束NY图的连通分量输入一个数20134562.3 程序源代码#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum; /有向图的当前顶点数和弧数MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置int i=0; while(G.vexsi!=v) +i; return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示char v1,v2; int i,j,w; cout创建无向图endl请输入图G顶点和弧的个数:(4 6)不包括“()”G.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:(a b 3)不包括“()”v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.vexnum;void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) coutG.arcsij.adj ; coutadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; /*for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; */ cout图G邻接表创建成功！endl; return 1;void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10; int initqueue(linkqueue &q)/初始化队列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.rear; if(!q.front) return 0; q.front-next=NULL; return 1;int enqueue(linkqueue &q,int e)/入队 queueptr p; p=(queueptr)malloc(sizeof(qnode); if(!p) return 0; p-data=e; p-next=NULL; q.rear-next=p; q.rear=p; return 1;int dequeue(linkqueue &q,int &e)/出队 queueptr p; if(q.front=q.rear) return 0; p=q.front-next; e=p-data; q.front-next=p-next; if(q.rear=p) q.rear=q.front; free(p); return 1;int queueempty(linkqueue q)/判断队为空 if(q.front=q.rear) return 1; return 0;void bfstra(algraph gra)/广度优先遍历 int i,e; linkqueue q; for(i=0;i!=gra.vexnum;+i) visitedi=0; initqueue(q); for(i=0;i!=gra.vexnum;+i) if(!visitedi) visitedi=1; coutgra.verticesi.data; enqueue(q,i); while(!queueempty(q) dequeue(q,e); / cout e=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe) visitedwe=1; coutgra.verticeswe.data; enqueue(q,we); int dfs(algraph gra,int i);/声明DFSint dfstra(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); return 0;int dfs(algraph gra,int i) visitedi=1; int we1;/ coutivisitediendl; coutgra.verticesi.data;/ cout=0;we=nextadjvex(gra,gra.verticesi,we) / coutwevisitedweendl; we1=we; / coutnextadjvex(gra,gra.verticesi,we)endl; if(visitedwe=0) / cout dfs(gra,we);/endl; / coutiwe1endl; we=we1; / coutnextadjvex(gra,gra.verticesi,we)endl; return 12;int bfstra_fen(algraph gra)/求连通分量 int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); coutendl; return 0;typedef struct int adjvex; int lowcost; closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u) int k,j,i; closedge closedge_a20; k=localvex(G,u);/ coutkendl; for(j=0;j!=G.vexnum;+j) if(j!=k) closedge_aj.adjvex=u; closedge_aj.lowcost=G.arcskj.adj; for(i=1;i!=G.vexnum;+i) k=minimum(closedge_a); coutk; coutclosedge_ak.adjvex G.vexskendl; closedge_ak.lowcost=0; for(j=0;j!=G.vexnum;+j) if(G.arcskj.adjp-lowcost) s=p-lowcost; return s;*/int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;void kruscal_arc(MGraph_L G,algraph gra) edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; / coutxym;/ coutendl; buf=find(acrvisited,x); edf=find(acrvisited,y); / coutbuf edfendl; edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; void main() algraph gra; MGraph_L G; int i,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); vnode v; coutendl#注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值。endlendl; cout菜单endlendl; cout0、显示该图的邻接矩阵endl; cout1、显示该图的邻接表endl; cout2、深度优先遍历endl; cout3、广度优先遍历endl; cout4、最小生成树PRIM算法endl; cout5、最小生成树KRUSCAL算法endl; cout6、该图的连通分量endlendl; int s; char y=y; while(y=y) cout请选择菜单：s; switch(s) case 0: cout邻接矩阵显示如下：endl; ljjzprint(G); break; case 1: cout邻接表显示如下：endl; adjprint(gra); break; case 2: cout广度优先遍历：; bfstra(gra); coutendl; break; case 3: for(i=0;i!=gra.vexnum;+i) visitedi=0; cout深度优先遍历：; dfstra(gra); coutendl; break; case 4: for(i=0;i!=G.vexnum;+i) for(int j=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutprim:endl; prim(g,d); break; case 5: coutkruscal:endl; kruscal_arc(G,gra); break; case 6: cout连通分量:; bfstra_fen(gra); break; coutendly; if(y=n) break; 3 编译运行图3.1创建无向图G图3.2程序主菜单