求無向連通圖的生成樹

求無向連通圖的生成樹求無向連通圖的生成樹一、實(shí)驗(yàn)?zāi)康?1\*GB2⑴掌握圖的邏輯結(jié)構(gòu)=2\*GB2⑵掌握圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)=3\*GB2⑶驗(yàn)證圖的鄰接矩陣存儲(chǔ)及其遍歷操作的實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容（1）建立無向圖的鄰接矩陣存儲(chǔ)（2）對建立的無向圖，進(jìn)行深度優(yōu)先遍歷（3）對建立的無向圖進(jìn)行廣度優(yōu)先遍歷三、設(shè)計(jì)與編碼（1）本實(shí)驗(yàn)用到的理論知識(shí)（2）算法設(shè)計(jì)（3）編碼//圖抽象類型及其實(shí)現(xiàn).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);//參數(shù)vertexnum非法 inti,front,rear,k; Enode*q; //先生成不帶邊表的頂點(diǎn)表--即頂點(diǎn)為孤立頂點(diǎn)集 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);//參數(shù)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);//存在環(huán) 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<<"連通分量數(shù)="<<g1.DfsDravers(2)<<endl; cout<<"--------------"<<endl; if(g1.GetType()>2)cout<<"連通分量數(shù)="<<g1.Bfs()<<endl; if(g1.GetType()<3) { if(g1.TopoSort(stack,temp))cout<<"拓?fù)渑判虺晒?！\n"; elsecout<<"該圖有環(huán)！\n"; cout<<"部分或全部的拓?fù)湫蛄袨椋?頂點(diǎn)總數(shù)="<<g1.GetLen()<<")\n"; for(inti=0;i<temp;i++)cout<<stack[i]<<'\t';cout<<"已排序頂點(diǎn)數(shù)目="<<temp<<endl; }; delete[5]stack; //print