求无向连通图的生成树

求无向连通图的生成树求无向连通图的生成树一、实验目的=1\*GB2⑴掌握图的逻辑结构=2\*GB2⑵掌握图的邻接矩阵存储结构=3\*GB2⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容（1）建立无向图的邻接矩阵存储（2）对建立的无向图，进行深度优先遍历（3）对建立的无向图进行广度优先遍历三、设计与编码（1）本实验用到的理论知识（2）算法设计（3）编码//图抽象类型及其实现.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"Graph.h"#include"iostream.h"intGraph::Find(intkey,int&k){ intflag=0; for(inti=0;i<VertexLen;i++) if(A[i].data.key==key){k=i;flag=1;break;}; returnflag;};intGraph::CreateGraph(intvertexnum,Edge*E,intedgenum){ //由边的集合E(E[0]~E[VertexNum-1])，生成该图的邻接表表示 if(vertexnum<1)return(-1);//参数vertexnum非法 inti,front,rear,k; Enode*q; //先生成不带边表的顶点表--即顶点为孤立顶点集 A=newVnode[vertexnum]; if(!A)return(0);//堆耗尽 for(i=0;i<vertexnum;i++) { A[i].data.key=i; A[i].tag=0; A[i].data.InDegree=A[i].data.OutDegree=A[i].tag=0; A[i].first=0; }; VertexLen=vertexnum; //在生成边表 if(edgenum<0)return(1);//无边的图 for(i=0;i<edgenum;i++) { front=E[i].Head;rear=E[i].Tail; if(!Find(rear,k)||!Find(front,k))return(-2);//参数E非法 q=newEnode; if(!q)return(0); q->key=front; q->Weight=E[i].weight; q->next=A[rear].first; A[rear].first=q; A[rear].data.OutDegree++; A[front].data.InDegree++; if(Type>2) { q=newEnode; if(!q)return(0); q->key=rear; q->next=A[front].first; A[pe->key].tag--; if(A[pe->key].tag==0){que[r++]=pe->key;A[pe->key].tag=-1;}; }; }; num=r; if(r<VertexLen)return(0);//存在环 return1;};intmain(intargc,char*argv[]){Graphg1(1); intnum=5,temp=1; int*stack=newint[5]; Edgeb[12]; b[0].Head=1;b[0].Tail=0;b[0].weight=1; b[1].Head=3;b[1].Tail=1;b[1].weight=1; b[2].Head=0;b[2].Tail=2;b[2].weight=1; b[3].Head=1;b[3].Tail=4;b[3].weight=1; b[4].Head=4;b[4].Tail=2;b[4].weight=1; b[5].Head=4;b[5].Tail=3;b[5].weight=1; // b[6].Head=0;b[6].Tail=1;b[6].weight=1; b[7].Head=1;b[7].Tail=3;b[7].weight=1; b[8].Head=2;b[8].Tail=0;b[8].weight=1; b[9].Head=4;b[9].Tail=1;b[9].weight=1; b[10].Head=2;b[10].Tail=4;b[10].weight=1; b[11].Head=3;b[11].Tail=2;b[11].weight=1; //b=={{1,0,1},{3,1,1},{0,2,1},(1,4,1},{4,2,1},{2,3,1}}; g1.CreateGraph(num,b,6); if(g1.GetType()>2)cout<<"连通分量数="<<g1.DfsDravers(2)<<endl; cout<<"--------------"<<endl; if(g1.GetType()>2)cout<<"连通分量数="<<g1.Bfs()<<endl; if(g1.GetType()<3) { if(g1.TopoSort(stack,temp))cout<<"拓扑排序成功！\n"; elsecout<<"该图有环！\n"; cout<<"部分或全部的拓扑序列为：(顶点总数="<<g1.GetLen()<<")\n"; for(inti=0;i<temp;i++)cout<<stack[i]<<'\t';cout<<"已排序顶点数目="<<temp<<endl; }; delete[5]stack; //print