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

摘要图是一种较线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：图；存储；遍历；深度；广度目录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;return1;}intdequeue(linkqueue&q,int&e)//出队{queueptrp;if(q.front==q.rear)return0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear==p)q.rear=q.front;free(p);return1;}intqueueempty(linkqueueq)//判断队为空{if(q.front==q.rear)return1;return0;}voidbfstra(algraphgra)//广度优先遍历{inti,e;linkqueueq;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){visited[i]=1;coutgra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){dequeue(q,e);//coute;for(we=first