求無向連通圖的生成樹

1、求無向連通圖的生成樹一、實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的邏輯結(jié)構(gòu)掌握?qǐng)D的鄰接矩陣存儲(chǔ)結(jié)構(gòu)驗(yàn)證圖的鄰接矩陣存儲(chǔ)及其遍歷操作的實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1建立無向圖的鄰接矩陣存儲(chǔ)2對(duì)建立的無向圖，進(jìn)行深度優(yōu)先遍歷3對(duì)建立的無向圖進(jìn)行廣度優(yōu)先遍歷三、設(shè)計(jì)與編碼1本實(shí)驗(yàn)用到的理論知識(shí) 2算法設(shè)計(jì)3編碼/ 圖抽象類型及其實(shí)現(xiàn) .cpp : Defines the entry point for the console application./#include "stdafx.h"#include "Graph.h"#include "iostream.h"int Gr

2、aph:Find( int key, int &k)int flag=0;for (int i=0;i<VertexLen;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 (vertex num <1) return (-1); / 參數(shù) vertex num 非法int i,front,rear,k;Enode *q;/

3、 先生成不帶邊表的頂點(diǎn)表 - 即頂點(diǎn)為孤立頂點(diǎn)集A=newVnodevertexnum;if (!A) return (0); / 堆耗盡for (i=0;i<vertexnum;i+)Ai.data.key=i;Ai.tag=0;Ai.data.InDegree=Ai.data.OutDegree=Ai.tag=0;Ai.first=0;VertexLen=vertexnum;/ 在生成邊表if (edgenum<0)return (1); / 無邊的圖for (i=0;i<edgenum;i+) front=Ei.Head;rear=Ei.Tail;if (!Find(r

4、ear,k) | !Find(front,k)return (-2); / 參數(shù)E非法q=newEnode; if (!q) return (0); q->key=front; q->Weight=Ei.weight; q->next=Arear.first; Arear.first=q;Arear.data.OutDegree+; Afront.data.InDegree+;if (Type>2)q=newEnode;if (!q) return (0); q->key=rear; q->next=Afront.first;Afront.first=q;q

5、->Weight=Ei.weight;return (1);void Graph:Dfs( int key, int &flag)/static run=1;Enode *w;Akey.tag=flag;if (Type>2)cout<< " 連通分量 =" <<flag<< 't' cout<< " 頂點(diǎn)鍵值 =" <<key<<endl; for (w=Akey.first;w ;w=w->next) if (!Aw->key.ta

6、g)Dfs(w->key,flag);int Graph:DfsDravers( int v0) / 從指定頂點(diǎn)深度遍歷int i,k,componentnum=1;/if(Type<3)return(-1);/ 不考慮由向圖 /cout<<"begainn"if (!(Find(v0,k)cout<< "find=" <<k<<endl; return (0); / 初 始結(jié)點(diǎn)vO不存在if (Type>2)cout<< "- 連通分量 " <<

7、;componentnum<"<-" <<endl; Dfs(k,componentnum);componentnum+;for (i=O;i<VertexLen;i+)if (!Ai.tag)if (Type>2)cout<< "- 連通分量" <<componentnum<"<-" <<endl; Dfs(i,componentnum);componentnum+;return (componentnum-1);int Graph:Bfs()int

8、 i,comp=1;/comp= 連通分量的標(biāo)記， 、.struct queue int key;queue * next;Enode *pe;queue *f,*r,*q,*p=new queue;if (!p) return (-1);/ 堆耗盡p->next=0;f=r=p;/ 生成空隊(duì)列for (i=0;i<VertexLen;i+)Ai.tag=0; / 初始化已訪問標(biāo)志 for (i=0;i<VertexLen;i+)if (Ai.tag=0)Ai.tag=comp;/ 入隊(duì)該頂點(diǎn)的 keyp=newqueue;if (!p) return (-1);p->

9、key=Ai.data.key;p->next=0;f->next=p;r=p;while (f->next) / 當(dāng)隊(duì)非空時(shí)/ 出隊(duì)一頂點(diǎn)q=f->next;if (Type>2)cout<< "連通分量 " <<comp<<'t' ;cout<< "頂點(diǎn)鍵值 ="<<q->key<<endl; f->next=q->next;if (q=r)r=f;/與q連接的未訪問的頂點(diǎn)入隊(duì)pe=Aq->key.first;

10、while (pe)if (Ape->key.tag=0)/ 入隊(duì)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;/ 釋放隊(duì)列while (f)p=f->next; delete f;f=p;return comp-1; / 返回連通

11、分量數(shù);/*int Graph:TopoSort( int *que, int &num)que順序隊(duì)列保存了拓?fù)渑判虻慕Y(jié)果，f和r為que的頭尾指示；loop 用于判有無環(huán)int i,f=0,r=0,index,loop=1;Enode *pe;num=0;for (i=0;i<VertexLen;i+)Ai.tag=Ai.data.InDegree;/ 初始化入度到 tag 域for (i=0;i<VertexLen;i+) if (Ai.tag=0)quer+=i;Ai.ta g=-1;loop=0;if (loop) return (0);while (f<r

12、)/ 棧未處理完index=quef+;for (pe=Aindex.first;pe;pe=pe->next)Ape->key.tag-;if (Ape->key.tag=0)quer+=pe->key;Ape->key.tag=-1;5;num=r;if (r<VertexLen) return (0); / 存在環(huán)return 1;int main( int argc, char* argv) Graph g1(1);int num=5,temp=1;int *stack= new int 5;Edge b12;b0.Head=1;b0.Tail=0;

13、b0.weight=1;b1.Head=3;b1.Tail=1;b1.weight=1;b2.Head=0;b2.Tail=2;b2.weight=1;b3.Head=1;b3.Tail=4;b3.weight=1;b4.Head=4;b4.Tail=2;b4.weight=1;b5.Head=4;b5.Tail=3;b5.weight=1;/b6.Head=0;b6.Tail=1;b6.weight=1;b7.Head=1;b7.Tail=3;b7.weight=1;b8.Head=2;b8.Tail=0;b8.weight=1;b9.Head=4;b9.Tail=1;b9.weight=1

14、;b10.Head=2;b10.Tail=4;b10.weight=1;b11.Head=3;b11.Tail=2;b11.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<<

15、 " 連通分量數(shù) =" <<g1.Bfs()<<endl;if (g1.GetType()<3)if (g1.TopoSort(stack,temp)cout<< " 拓?fù)渑判虺晒Γ?n" ; else cout<< " 該圖有環(huán)！ n" ;cout<< "局部或全部的拓?fù)湫蛄袨椋?( 頂點(diǎn)總數(shù)=" <<g1.GetLen()<< ")n" ;for (int i=0;i<temp;i+)cout<<stacki