《求无向连通图的生成树.docx》由会员分享，可在线阅读，更多相关《求无向连通图的生成树.docx（7页珍藏版）》请在三一文库上搜索。
1、求无向连通图的生成树求无向连通图的生成树一、实验目的掌握图的逻辑结构掌握图的邻接矩阵存储结构验证图的邻接矩阵存储及其遍历操作的实现二、实验内容(1)建立无向图的邻接矩阵存储(2)对建立的无向图 ,进行深度优先遍历(3)对建立的无向图进行广度优先遍历三、设计与编码(1)本实验用到的理论知识(2)算法设计(3)编码/ 图抽象类型及其实现、 cpp : Defines the entry point for theconsole application、/#includestdafx、h#includeGraph 、h#includeiostream 、hintGraph:Find(intkey,
2、int&k)intforflag=0;( inti=0;iVertexLen;i+)if (Ai、data 、key=key)k=i;flag=1;returnflag;break ;intGraph:CreateGraph(intvertexnum,Edge *E,intedgenum) / 由边的集合 E(E0EVertexNum-1), 生成该图的邻接表表示 if (vertexnum1) return (-1); / 参数 vertexnum 非法int i,front,rear,k; Enode *q;求无向连通图的生成树/ 先生成不带边表的顶点表 - 即顶点为孤立顶点集A=new
3、Vnodevertexnum;if (!A) return (0); / 堆耗尽 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 、
4、OutDegree+;Afront、data 、InDegree+;if (Type2)q=new Enode;if (!q) return (0);q-key=rear;q-next=Afront、first;Afront、first=q;q-Weight=Ei、weight;求无向连通图的生成树;return (1);void Graph:Dfs(intkey, int&flag)/static run=1;Enode *w;Akey 、tag=flag;if (Type2)cout 连通分量 =flag t ; cout 顶点键值 = keynext)if (!Aw-key、tag)Df
5、s(w-key,flag);intGraph:DfsDravers(intv0)/ 从指定顶点深度遍历inti,k,componentnum=1;/if(Type3)return(-1);/coutbegain、if (!(Find(v0,k)cout不考虑由向图n;find=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;
6、/ 初始化已访问标志for (i=0;ikey=Ai 、data 、key; p-next=0;f-next=p;r=p;while (f-next)/ 当队非空时 / 出队一顶点 q=f-next;if (Type2)cout 连通分量 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=
7、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;return comp-1;/ 返回连通分量数;/*intGraph:TopoSort(int*que, int&num) /que 顺序队列保存了拓扑排序的结果 ,f 与r 为que的头尾指示;loop 用于判有无环inti,f=0,r=0,index,loop=1;Enode *pe;num=0;fo
8、r (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 、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
9、、Bfs()endl; if (g1 、GetType()3)if (g1 、TopoSort(stack,temp)cout 拓扑排序成功！ n ; else cout 该图有环！ n ;cout 部分或全部的拓扑序列为 :( 顶点总数 =g1、 GetLen() )n ;for ( inti=0;itemp;i+)coutstackit;cout 已排求无向连通图的生成树序顶点数目 = tempendl;delete 5stack;/printf(Hello World!n);return0;四、运行与调试运行结果为 :该图有环！部分或全部拓扑序列为:20已排序顶点数目 =2Press any key to continue五、总结与心得