《求无向连通图的生成树.pdf》由会员分享，可在线阅读，更多相关《求无向连通图的生成树.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、求无向连通图的生成树求无向连通图的生成树一、实验目的掌握图的逻辑结构掌握图的邻接矩阵存储结构验证图的邻接矩阵存储及其遍历操作的实现二、实验内容1建立无向图的邻接矩阵存储2对建立的无向图，进行深度优先遍历3对建立的无向图进行广度优先遍历三、设计与编码1本实验用到的理论知识2算法设计3编码/ 图抽象类型及其实现.cpp : Defines the entry point for theconsole application./#include stdafx.h#include Graph.h#include iostream.hint Graph:Find(int key,int &k)int f
2、lag=0;for(int i=0;iVertexLen;i+)if(Ai.data.key=key)k=i;flag=1;break;return flag;int Graph:CreateGraph(int vertexnum,Edge *E,int edgenum)/由边的集合E(E0EVertexNum-1)，生成该图的邻接表表示if(vertexnum1)return(-1);/参数vertexnum非法int i,front,rear,k;Enode *q;/先生成不带边表的顶点表-即顶点为孤立顶点集A=new Vnodevertexnum;if(!A)return(0);/堆耗尽
3、for(i=0;ivertexnum;i+)Ai.data.key=i;Ai.tag=0;Ai.data.InDegree=Ai.data.OutDegree=Ai.tag=0;Ai.first=0;VertexLen=vertexnum;/在生成边表if(edgenum0)return(1);/无边的图for(i=0;ikey=front;q-Weight=Ei.weight;q-next=Arear.first;Arear.first=q;Arear.data.OutDegree+;Afront.data.InDegree+;if(Type2)q=new Enode;if(!q)retur
4、n(0);q-key=rear;q-next=Afront.first;Afront.first=q;q-Weight=Ei.weight;return(1);void Graph:Dfs(int key,int &flag)/static run=1;Enode *w;Akey.tag=flag;if(Type2)cout连通分量=flagt;cout顶点键值=keynext)if(!Aw-key.tag)Dfs(w-key,flag);int Graph:DfsDravers(int v0) /从指定顶点深度遍历int i,k,componentnum=1;/if(Type3)return
5、(-1);/不考虑由向图/coutbegain.n;if(!(Find(v0,k)coutfind=k2)cout-连通分量componentnum-endl;Dfs(k,componentnum);componentnum+;for(i=0;i2)cout-连通分量componentnum-next=0;f=r=p;/生成空队列for(i=0;iVertexLen;i+)Ai.tag=0;/初始化已访问标志for(i=0;ikey=Ai.data.key;p-next=0;f-next=p;r=p;while(f-next)/当队非空时/出队一顶点q=f-next;if(Type2)cout
6、连通分量compt;cout顶点键值=keynext=q-next;if(q=r)r=f;/与q连接的未访问的顶点入队pe=Aq-key.first;while(pe)if(Ape-key.tag=0)/入队if(!(p=new queue)return(-1);Ape-key.tag=comp;p-key=pe-key;p-next=0;if(f=r)f-next=p;r-next=p;r=p;pe=pe-next;/end of (pe)delete q;/end of (f-next)comp+;/enf of if;/释放队列while(f)p=f-next;delete f;f=p;
7、return comp-1;/返回连通分量数;/*int Graph:TopoSort(int *que,int &num)/que顺序队列保存了拓扑排序的结果，f和r为que的头尾指示；loop用于判有无环int i,f=0,r=0,index,loop=1;Enode *pe;num=0;for(i=0;iVertexLen;i+)Ai.tag=Ai.data.InDegree;/初始化入度到tag域for(i=0;iVertexLen;i+)if(Ai.tag=0)quer+=i;Ai.tag=-1;loop=0;if(loop)return(0);while(fnext)Ape-key
8、.tag-;if(Ape-key.tag=0)quer+=pe-key;Ape-key.tag=-1;num=r;if(r2)cout连通分量数=g1.DfsDravers(2)endl;cout-2)cout连通分量数=g1.Bfs()endl;if(g1.GetType()3)if(g1.TopoSort(stack,temp)cout拓扑排序成功！n;else cout该图有环！n;cout部分或全部的拓扑序列为：(顶点总数=g1.GetLen()n;for(int i=0;itemp;i+)coutstackit;cout已排序顶点数目=tempendl;delete5stack;/printf(Hello World!n);return 0;四、运行与调试运行结果为：该图有环！该图有环！部分或全部拓扑序列为：部分或全部拓扑序列为： =52 20 0已排序顶点数目已排序顶点数目=2=2Press any key to continuePress any key to continue五、总结与心得