图的遍历和生成树求解问题的研究与实现[1]

数据结构课程设计设计说明书图的遍历和生成树求解问题的研究与实现学生姓名秦洁学号0621024014班级信管061成绩指导教师魏佳计算机科学与技术系2008年3月8日数据结构课程设计评阅书题目图的遍历和生成树求解问题的研究与实现学生姓名秦洁学号0621024014指导教师评语及成绩指导教师签名：年月日答辩评语及成绩答辩教师签名：年月日教研室意见总成绩：室主任签名：年月日课程设计任务书2007—2008学年第一学期专业：信息管理与信息系统学号：0621024014姓名：秦洁课程设计名称：数据结构课程设计设计题目：图的遍历和生成树求解问题的研究与实现完成期限：自2008年2月25日至2008年3月7日共2周设计依据、要求及主要内容（可另加附页）：设计依据：数据结构算法设计要求：先任意创建一个图；图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。主要内容：对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储，并完成图的DFS和BFS操作。指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要图是一种较线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：图；存储；遍历；深度；广度目录1课题描述……………………………………………………………………………12设计过程……………………………………………………………………………22.1设计思路……………………………………………………………………22.2设计流程图…………………………………………………………………32.3程序源代码…………………………………………………………………43编译运行…………………………………………………………………………17总结…………………………………………………………………………………19参考文献……………………………………………………………………………201课题描述图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子节点）相关，但只能和上一层中一个元素（即其双亲节点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。开发工具：VisualC++6.02设计过程本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.1设计思路这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.2设计流程图开始创建图G用邻接表存储图Ify=’y’NY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母Ify=’y’结束NY图的连通分量输入一个数20134562.3程序源代码#includeiostream#includemalloc.husingnamespacestd;#defineint_max10000#defineinf9999#definemax20//…………………………………………邻接矩阵定义……………………typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;//有向图的当前顶点数和弧数}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示{charv1,v2;inti,j,w;cout…………创建无向图…………endl请输入图G顶点和弧的个数:(46)不包括“()”endl;cinG.vexnumG.arcnum;for(i=0;i!=G.vexnum;++i){cout输入顶点iendl;cinG.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){cout输入一条边依附的顶点和权:(ab3)不包括“()”endl;cinv1v2w;//输入一条边依附的两点及权值i=localvex(G,v1);//确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout图G邻接矩阵创建成功！endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)coutG.arcs[i][j].adj;coutendl;}}intvisited[max];//访问标记intwe;typedefstructarcnode//弧结点{intadjvex;//该弧指向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧char*info;//该弧信息}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedefstruct//图的定义{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;//…………………………………………队列定义……………………typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;//………………………………………………………………………typedefstructacr{intpre;//弧的一结点intbak;//弧另一结点intweight;//弧的权}edg;intcreatadj(algraph&gra,MGraph_LG)//用邻接表存储图{inti=0,j=0;arcnode*arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc-adjvex=j;gra.vertices[i].firstarc=arc;arc-nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){tem=(arcnode*)malloc(sizeof(arcnode));tem-adjvex=j;gra.vertices[i].firstarc=tem;tem-nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].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.vertices[i].firstarc;while(p!=NULL){coutp-adjvex;p=p-nextarc;}coutendl;}*/cout图G邻接表创建成功！endl;return1;}voidadjprint(algraphgra){inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;couti;p=gra.vertices[i].firstarc;while(p!=NULL){coutp-adjvex;p=p-nextarc;}coutendl;}}intfirstadjvex(algraphgra,vnodev)//返回依附顶点V的第一个点//即以V为尾的第一个结点{if(v.firstarc!=NULL)returnv.firstarc-adjvex;}intnextadjvex(algraphgra,vnodev,intw)//返回依附顶点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;returnp-adjvex;}if(p-adjvex==w&&p-nextarc==NULL)return-10;}intinitqueue(linkqueue&q)//初始化队列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front-next=NULL;return1;}intenqueue(linkqueue&q,inte)//入队{queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return