求无向连通图的生成树.doc

求无向连通图的生成树一、实验目的掌握图的逻辑结构掌握图的邻接矩阵存储结构验证图的邻接矩阵存储及其遍历操作的实现二、实验内容（1）建立无向图的邻接矩阵存储（2）对建立的无向图，进行深度优先遍历（3）对建立的无向图进行广度优先遍历三、设计与编码（1）本实验用到的理论知识（2）算法设计（3）编码/ 图抽象类型及其实现.cpp : Defines the entry point for the console application./#include stdafx.h#include Graph.h#include iostream.hint Graph:Find(int key,int &k)int flag=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);/堆耗尽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)return(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(-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连通分量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;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.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已排序顶点数目=temp