山東大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗報告八

1、山東大學(xué)軟件工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實驗報告學(xué)號：姓名：班級：軟件工程 2014 級 2 班實驗題目：圖的操作實驗學(xué)時： 實驗日期：實驗?zāi)康模赫莆請D的基本概念，描述方法；遍歷方法。硬件環(huán)境：實驗室軟件環(huán)境：Vistual Studio 2013實驗步驟與內(nèi)容：實驗內(nèi)容：1、創(chuàng)建圖類。二叉樹的存儲結(jié)構(gòu)使用鄰接矩陣或鏈表。2、提供操作 :遍歷、 BFS、DFS3、對建立好的圖，執(zhí)行上述各操作。4、輸出生成樹。5、輸出最小生成樹。代碼體：Adjacencywdigraph.h#ifndefADJACENCYWDIGRAPH_H#defineADJACENCYWDIGRAPH_HclassAdjacenc

2、yWDigraph friendclassAdjacencyWGraph;public :AdjacencyWDigraph( intVertices = 10,AdjacencyWDigraph();intnoEnge = 0);bool Exist(inti,intj)const ;intEdges()const returne; intVertices()const returnn; AdjacencyWDigraph & Add( inti,intj,const int & w = 1);AdjacencyWDigraph & Delete(inti,intj)

3、;intOutDegree(int i)const ;intInDegree(inti)const ;voidInitializePos() pos =new intn + 1; voidDeactivatePos() delete pos; intBegin(inti);intNextVertex(inti);voidBFS(intv,intreach,intlabel = 1);voidDFS(intv,intreach,intlabel = 1);bool Connected( int& x);int* SpanningTree();int* SpanningMinTree();

4、voidOutPut();private:intMinNum();intMin( intv,intreach);bool Connecting(inti);voiddfs( intv,intreach,intlabel);intNoEdge, n, e;int*a;int*pos;#endifAdjacencywdigraph.cpp#include <iostream>#include <queue>usingnamespace std;#include"adjacencywdigraph.h"AdjacencyWDigraph :Adjacenc

5、yWDigraph(intVertices ,intnoEdge)n =Vertices ;e = 0;NoEdge = noEdge;a =new int *n + 1;for ( inti = 1; i <= n; i+)ai =new int n + 1;for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j+)aij = NoEdge;AdjacencyWDigraph :AdjacencyWDigraph()for ( inti = 1; i <= n; i+)delete ai;delete a;boolAd

6、jacencyWDigraph :Exist( if ( i < 1 | j < 1 | iint> n |i ,intj ) const j > n | ai j = NoEdge)returnfalse ;returntrue ;AdjacencyWDigraph & AdjacencyWDigraph :Add( inti ,intj ,constint & w)if( i < 1 |j < 1 |i > n |j > n)cout <<" 錯誤 ! 點 " << i <&l

7、t;" 或點 " << j <<" 不存在 , 無法添加邊 " << endl;elseif(ai j != NoEdge)cout <<" 錯誤 ! 該邊已存在 , 無法再添加 " << endl;else a i j =w;e+;return* this ;AdjacencyWDigraph & AdjacencyWDigraph :Delete(inti ,intj )if( i < 1 |j < 1 |i > n |j > n | ai

8、 j = NoEdge)cout <<" 錯誤 ! 該邊不存在 , 無法刪除 " << endl;else a i j = NoEdge;e-;return* this ;intAdjacencyWDigraph :OutDegree(inti )const if( i < 1 |i > n)cout <<" 錯誤 , 該點不存在 !" << endl;return0;else intsum = 0;for ( intj = 1; j <= n; j+)if(ai j != NoEdge)

9、sum+;returnsum;intAdjacencyWDigraph :InDegree(inti )const if( i < 1 |i > n)cout <<" 錯誤 , 該點不存在 !" << endl;return0;else intsum = 0;for ( intj = 1; j <= n; j+)if(aji != NoEdge)sum+;returnsum;intAdjacencyWDigraph :Begin(inti )if( i < 1 |i > n)cout <<" 錯誤

10、, 該點不存在 !" << endl;return0;else for ( intj = 1; j <= n; j+)if(ai j != NoEdge)pos i = j;returnj;pos i = n + 1;return0;intAdjacencyWDigraph :NextVertex(inti )if( i < 1 |i > n)cout <<" 錯誤 , 該點不存在 !" << endl;return0;else for ( intj = posi + 1; j <= n; j+)if(a

11、i j != NoEdge)pos i = j;returnj;pos i = n + 1;return0;voidAdjacencyWDigraph :BFS( intv,intreach ,intlabel )if( v < 1 |v > n)cout <<" 錯誤 , 該點不存在!"<< endl;return ;queue<int > q;InitializePos();reach v =label ;q.push( v);while (!q.empty()intw = q.front();q.pop();intu =

12、 Begin(w);while (u)if(!reach u)q.push(u);reach u =label;u = NextVertex(w);DeactivatePos();voidAdjacencyWDigraph :dfs(reach v =label ;intu = Begin(v);while (u)if(! reach u)dfs(u,reach ,u = NextVertex(v);intlabelv,);intreach ,intlabel )voidAdjacencyWDigraph :DFS( intv,intreach ,intlabel )if( v < 1

13、|v > n)cout <<" 錯誤 , 該點不存在 !" << endl;return ;InitializePos();dfs( v,reach ,label );DeactivatePos();voidAdjacencyWDigraph :OutPut()for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j+)cout << aij <<"t"cout << endl;boolAdjacencyWDigraph :Con

14、necting(inti )int*reach =new int n + 1;for ( intj = 1; j <= n; j+)reachj = 0;BFS(i , reach, 1);for ( intj = 1; j <= n; j+)if(!reachj)delete reach;returnfalse ;delete reach;returntrue ;boolAdjacencyWDigraph :Connected(int & x)bool *flag =new bool n + 1;for ( inti = 1; i <= n; i+)flagi =

15、Connecting(i);for ( inti = 1; i <= n; i+)if(flagi)x = i;returntrue ;returnfalse ;intAdjacencyWDigraph :Min(intv,intreach )intk = 0, min = 0;for ( inti = 1; i <= n; i+)if(! reach i && ak = i;min = avi;vi != NoEdge && !min)elseif(! reach i && avi != NoEdge && min

16、> avi)k = i;min = avi;returnk;int *AdjacencyWDigraph :SpanningTree()intx;if(!Connected(x)cout <<" 該圖不是連通圖 , 無法生成樹 !" << endl;return0;else InitializePos();queue<int > q;int*b =new int *n + 1;for ( inti = 1; i <= n; i+)bi =new int n + 1;for ( inti = 1; i <= n; i+)f

17、or ( intj = 1; j <= n; j+)bij = 0;int*reach =new int n + 1;for ( inti = 1; i <= n; i+)reachi = 0;reachx = 1;q.push(x);while (!q.empty()intw = q.front();q.pop();intu = Begin(w);while(u)if(!reachu)q.push(u);bwu = awu;reachu = 1;u = NextVertex(w);delete reach;DeactivatePos();returnb;intAdjacencyW

18、Digraph :MinNum()intk = 0, m = 0;for ( inti = 1; i <= n; i+)if(Connecting(i)intmin = 0;for ( intj = 1; j <= n; j+)if(aij != NoEdge && !min)min = aij;elseif(aij != NoEdge && min > aij)min = aij;if(m && m > min)m = min;k = i;elseif(!m)m = min;k = i;returnk;int *Adja

19、cencyWDigraph :SpanningMinTree()intx;if(!Connected(x)cout <<" 該圖不是連通圖 , 無法生成樹 !" << endl;return0;else int*b =new int *n + 1;for ( inti = 1; i <= n; i+)bi =new int n + 1;for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j+)bij = 0;int*reach =new int n + 1;for ( inti =

20、1; i <= n; i+)reachi = 0;x = MinNum();reachx = 1;intk1, k2, z, min = 1;while (min)min = 0;for ( inti = 1; i <= n; i+)if(reachi)k2 = Min(i, reach);if(k2 && !min)min = aik2;z = i;k1 = k2;elseif(k2 && min > aik2)min = aik2;z = i;k1 = k2;reachk1 = 1;bzk1 = azk1;delete reach;retu

21、rnb;Adjacencywgraph.h#ifndefADJACENCYWGRAPH_H#defineADJACENCYWGRAPH_H#include"adjacencywdigraph.h"classAdjacencyWGraph : publicAdjacencyWDigraph public :AdjacencyWGraph(intVertices= 10,intnoEdge = 0):AdjacencyWGraph& Add( inti,intj,constint & w = 1);AdjacencyWDigraph ( Vertices,noE

22、dge)AdjacencyWGraph& Delete(inti,intj);intDegree( inti )returnOutDegree( i ); bool Connected();int * SpanningTree();int * SpanningMinTree();intMinNum();#endifAdjacencywgraph.cpp#include <iostream>#include <queue>usingnamespace std;#include"adjacencywgraph.h"AdjacencyWGraph&

23、amp; AdjacencyWGraph:Add( inti ,intj ,constint & w)if( i < 1 |j < 1 |i > n |j > n)cout <<" 錯誤 ! 點 " << i <<" 或點 " << j <<" 不存在 , 無法添加邊 " << endl;elseif(ai j != NoEdge)cout <<" 錯誤 ! 該邊已存在 , 無法再添加 " <&

24、lt; endl;else a i j =w;a j i =w;e+;return* this ;AdjacencyWGraph& AdjacencyWGraph:Delete(inti ,intj )if( i < 1 |j < 1 |i > n |j > n | ai j = NoEdge)cout <<" 錯誤 ! 該邊不存在 , 無法刪除 " << endl;else a i j = NoEdge;a j i = NoEdge;e-;return* this ;boolAdjacencyWGraph:Conne

25、cted()int*reach =new int n + 1;for ( inti = 1; i <= n; i+)reachi = 0;BFS(1, reach, 1);for ( inti = 1; i <= n; i+)if(!reachi)returnfalse ;returntrue ;int *AdjacencyWGraph:SpanningTree()if(!Connected()cout <<" 該圖不是連通圖 , 無法生成樹 !" << endl;return0;else InitializePos();queue<

26、;int > q;int*b =new int *n + 1;for ( inti = 1; i <= n; i+)bi =new int n + 1;for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j+)bij = 0;int*reach =new int n + 1;for ( inti = 1; i <= n; i+)reachi = 0;reach1 = 1;q.push(1);while (!q.empty()intw = q.front();q.pop();intu = Begin(w);while

27、(u)if(!reachu)q.push(u);bwu = buw = awu;reachu = 1;u = NextVertex(w);DeactivatePos();delete reach;returnb;intAdjacencyWGraph:MinNum()intd = 0, e = 0, min = 0;for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j+)if(aij != NoEdge && !min)min = aij;d = i;e = j;elseif(aij != NoEdge &&

28、amp; aij < min)min = aij;d = i;e = j;returnd;int *AdjacencyWGraph:SpanningMinTree()if(!Connected()cout <<" 該圖不是連通圖 , 無法生成樹 !" << endl;return0;else int*b =new int *n + 1;for ( inti = 1; i <= n; i+)bi =new int n + 1;for ( inti = 1; i <= n; i+)for ( intj = 1; j <= n; j

29、+)bij = 0;int*reach =new int n + 1;for ( inti = 1; i <= n; i+)reachi = 0;intx = MinNum();reachx = 1;intk1, k2, z, min = 1;while (min)min = 0;for ( inti = 1; i <= n; i+)if(reachi)k2 = Min(i, reach);if(k2 && !min)min = aik2;z = i;k1 = k2;elseif(k2 && min > aik2)min = aik2;z =

30、i;k1 = k2;reachk1 = 1;bzk1 = bk1z = azk1;delete reach;returnb;Test.cpp#include <iostream>usingnamespace std;#include"adjacencywdigraph.h"#include"adjacencywgraph.h"intmain()AdjacencyWDigraph *awd =new AdjacencyWDigraph (5, 0);AdjacencyWGraph *awg =new AdjacencyWGraph(5, 0);

31、/ 下面初始化一個有向圖 awd->Add(1, 5, 6); awd->Add(4, 3, 19);awd->Add(5, 4, 33);awd->Add(1, 2, 17);awd->Add(3, 4, 36);awd->Add(1, 3, 34);awd->OutPut();cout <<"*"<< endl;cout <<" 寬度優(yōu)先搜索開始 " << endl;cout <<" 請輸入起始點 : " <<endl

32、;intm;int*reach = new int 6;for( inti = 1; i <= 5; i+)reachi = 0;cin >> m;while (m < 1 | m>5)cout <<" 輸入錯誤！ " ;cin >> m;awd->BFS(m, reach);cout <<" 從點 " << m <<" 能搜索到的點有 : "<< endl;for( inti = 1; i <= 5; i+)if(reachi)cout << i <<"t"cout << endl;cout <<"*"<< endl;cout <<" 廣度優(yōu)先搜索開始 " << endl;cout <<" 請輸入起始點 : "<< endl;for( inti = 1; i <= 5; i+)re