《2022年求无向连通图的生成树.docx》由会员分享，可在线阅读，更多相关《2022年求无向连通图的生成树.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 求无向连通图的生成树一、试验目的把握图的规律结构把握图的邻接矩阵储备结构验证图的邻接矩阵储备及其遍历操作的实现二、试验内容1建立无向图的邻接矩阵储备2对建立的无向图,进行深度优先遍历3对建立的无向图进行广度优先遍历三、设计与编码1本试验用到的理论学问2算法设计3编码 / 图抽象类型及其实现 .cpp : Defines the entry point for the console application. / #include stdafx.h #include Graph.h #include iostream.h int Graph:Fi
2、nd int key, int &k int flag=0; for int i=0;iVertexLen;i+ if Ai.data.key=keyk=i;flag=1; break ; return flag; ; 名师归纳总结 int Graph:CreateGraphint vertexnum,Edge *E,int edgenum 第 1 页,共 7 页 / 由边的集合 EE0EVertexNum-1,生成该图的邻接表表示- - - - - - -精选学习资料 - - - - - - - - - if vertexnum1 return -1; / 参数vertexnum 非法int
3、 i,front,rear,k; Enode *q; / 先生成不带边表的顶点表A=new 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 edgenum0return 1; / 无边的图 for i=0;ikey=front; q-Weight=Ei.weight; q-
4、next=Arear.first; Arear.first=q; Arear.data.OutDegree+; Afront.data.InDegree+; if Type2 q=new Enode; if .q return 0; q-key=rear; q-next=Afront.first; 名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - Afront.first=q; q-Weight=Ei.weight; ; ; return 1; ; void Graph:Dfs int key, int &flag /static
5、run=1; Enode *w; Akey.tag=flag; if Type2cout 连通重量 =flag t ; cout 顶点键值 = keynext if .Aw-key.tagDfsw-key,flag; ; int Graph:DfsDravers int v0 / 从指定顶点深度遍历int i,k,componentnum=1; /ifType3return-1;/ 不考虑由向图 /coutbegain.n; if .Findv0,kcoutfind= k2cout - 连通重量 componentnum- endl; Dfsk,componentnum; componentn
6、um+; for i=0;i2cout - 连通重量 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 Type2cout 连通重量 compt ; cout 顶点键值 =keynext=q-next; if q=rr=f; / 与q连接的未拜访的顶点入队 pe=Aq-key.first; while pe if
7、 Ape-key.tag=0 / 入队名师归纳总结 - - - - - - -第 4 页,共 7 页精选学习资料 - - - - - - - - - if .p= new queue return -1; Ape-key.tag=comp; p-key=pe-key; p-next=0; if f=rf-next=p; r-next=p;r=p; ; pe=pe-next; ; /end of pe delete q; ; /end of f-next comp+; ; /enf of if ; / 释放队列 while fp=f-next; delete f;f=p; return comp
8、-1; / 返回连通重量数 ; /* int Graph:TopoSortint *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+ g=-1;loop=0; if loop return 0; while fnext 名师归纳总结 - - - - - - -第 5 页
9、,共 7 页精选学习资料 - - - - - - - - - Ape-key.tag-; ; if Ape-key.tag=0quer+=pe-key;Ape-key.tag=-1; ; num=r; if r2cout 连通重量数 = g1.DfsDravers2endl; cout- 2cout if g1.GetType3 连通重量数 = g1.Bfsendl; 名师归纳总结 - - - - - - -第 6 页,共 7 页精选学习资料 - - - - - - - - - if g1.TopoSortstack,tempcout 拓扑排序胜利！ n ; else cout 该图有环！ n ; ;cout 已排cout 部分或全部的拓扑序列为： 顶点总数= g1.GetLen n; for int i=0;itemp;i+coutstackit序顶点数目 = tempendl; ; delete 5stack; /printfHello World.n; return 0; 四、运行与调试运行结果为：该图有环！部分或全部拓扑序列为： 名师归纳总结 2 0 已排序顶点数目 =2 第 7 页,共 7 页Press any key to continue 五、总结与心得- - - - - - -