圖的隨機生成及歐拉(回)路的確定

1、離散數(shù)學實驗報告（2015 / 2016 學年 第 一 學期）題 目： 圖的隨機生成及歐拉（回）路的確定 專 業(yè) 信息安全 學 生 姓 名 班 級 學 號 指 導 教 師 指 導 單 位 計算機學院計算機科學與技術系 日 期 2015年12月29日 圖的隨機生成及歐拉（回）路的確定一、 實驗內容和要求內容：編程隨機生成n個結點的無向圖并能進行（半）歐拉圖的判定，若是則給出歐拉（回）路。要求：對給定n個結點，隨機生成鄰接矩陣以確定某無向簡單圖并進行歐拉圖和半歐拉圖的判定，若符合則給出至少一條歐拉回路或歐拉路。2、 實驗目的對給定n個結點，隨機生成鄰接矩陣以確定某無向簡單圖并進行歐拉圖和半歐拉圖的

2、判定，若符合則給出至少一條歐拉回路或歐拉路。三、實驗任務 1、輸入結點個數(shù)據(jù)生成隨機圖2、進行（半）歐拉圖的判定3、若是則給出歐拉（回）路。四、實驗內容 #include <iostream>#include <ctime>#include <cstdlib>using namespace std;class Eulerpublic:Euler(int num);Euler();void DFS(int begin); /公有的深度優(yōu)先搜索函數(shù)void inputEdge(); /輸入邊void PrintAM(); /打印鄰接矩陣void PrintRM(

3、); /打印可達性矩陣void Warshall(); /Warshall算法求可達性矩陣bool IsConnected(); / /判斷圖是否連通int IsEorSE(); /判斷圖是歐拉圖還是半歐拉圖bool isEuler;private:void DFS(int u,int v,bool *visited); / /私有的深度優(yōu)先搜索函數(shù)int n;int *a; /定義動態(tài)二維數(shù)組int *p; /定義可達性矩陣int *b; /存儲每個結點的度數(shù);Euler:Euler(int num) /構造函數(shù)isEuler=false;n=num;int i,j;a=new int*n;

4、for(i=0;i<n;i+)ai=new intn;for(j=0;j<n;j+)aij=0;p=new int*n;for(i=0;i<n;i+)pi=new intn;for(j=0;j<n;j+)pij=0;b=new intn;for(i=0;i<n;i+)bi=0;Euler:Euler()/析構函數(shù)int i;for(i=0;i<n;i+) delete ai;delete a;for(i=0;i<n;i+) delete pi;delete p;delete b;void Euler:inputEdge()srand(unsigned)

5、time(NULL); for(int i = 0; i < n; i+) for(int j = i + 1; j < n; j+) aij = 0+rand()%2; /隨機生成無向圖 aji=aij; for(int ii=0;ii<n;ii+)for(int jj=0;jj<n;jj+)if(aiijj=1)piijj=1;pjjii=1;void Euler:PrintAM()cout<<"隨機生成的圖為："<<endl;for(int i=0;i<n;i+)for(int j=0;j<n;j+)cout

6、<<aij<<" "cout<<endl;void Euler:Warshall()for(int i=0;i<n;i+)for(int j=0;j<n;j+)if(pji=1)for(int k=0;k<n;k+)if(pjk+pik>0)pjk=1;void Euler:PrintRM()cout<<"可達性矩陣："<<endl;for(int i=0;i<n;i+)for(int j=0;j<n;j+)cout<<pij<<&qu

7、ot; "cout<<endl;bool Euler:IsConnected()int i,j;bool flag=true; / /flag標記是否連通for(i=0;i<n;i+)for(j=0;j<n;j+)if(pij=0) /如果可達性矩陣中有一個元素為0， /就跳出循環(huán)，表示該圖不連通flag=false;break;if(!flag)break;if(!flag)cout<<"該圖不是連通的"elsefor(i=0;i<n;i+)for(j=i;j<n;j+)if(aij=1&&i!=j

8、) /由邊計算結點的度數(shù)bi+;bj+;return flag;int Euler:IsEorSE()int i,count=0,begin=-1;cout<<"每個結點的度數(shù)："<<endl;for(i=0;i<n;i+)cout<<i<<":"<<bi<<endl;for(i=0;i<n;i+)/計算奇數(shù)結點的個數(shù)if(bi%2!=0)count+;begin=i;/初始化開始結點，存在奇數(shù)結點，則將其中一個作為開始點if(begin=-1)/不存在奇數(shù)結點則將0作為

9、起始點begin=0;if(count=2)cout<<"該圖是半歐拉圖"<<endl;isEuler=true;/isEuler標記是否是（半）歐拉圖else if(count=0)cout<<"該圖是歐拉圖"<<endl;isEuler=true;return begin;void Euler:DFS(int begin)int i,j;bool *visited=new bool*n;/二維數(shù)組記錄每條邊是否被訪問過for(i=0;i<n;i+)/初始化visitedi=new booln;fo

10、r(j=0;j<n;j+)if(aij=1)visitedij=false;elsevisitedij=true;for(j=0;j<n;j+)if(!visitedbeginj) DFS(begin,j,visited);cout<<begin<<" "for(i=0;i<n;i+) delete visitedi;/釋放內存delete visited;void Euler:DFS(int u,int v,bool *visited)if(!visiteduv)/判斷邊<u,v>是否訪問過visiteduv=true

11、;visitedvu=true;/標記被訪問for(int i=0;i<n;i+)DFS(v,i,visited);cout<<v<<" " /輸出結點int main()int n,m,begin;bool flag;cout<<"輸入結點個數(shù):"cin>>n;Euler euler(n);euler.inputEdge();euler.PrintAM();euler.Warshall();euler.PrintRM();flag=euler.IsConnected();if(flag) begin

12、=euler.IsEorSE();if(euler.isEuler)cout<<"具體路徑為："euler.DFS(begin);cout<<endl;return 0;五、測試數(shù)據(jù)及其結果分析6、 調試過程中的問題可達性矩陣無法正確計算，調試后發(fā)現(xiàn)是算法中未正確定義循環(huán)變量七、程序設計總結1.掌握了與離散數(shù)學理論相關的編程實現(xiàn)思想和方法，掌握了歐拉圖和半歐拉圖的判定。2.利用鄰接矩陣表示存在的邊，通過Warshall算法求出無向圖的可達性矩陣，如果是連通的話，那么可達性矩陣中每一個元素都應該為1，否則存在元素為0。3.多次利用動態(tài)二維數(shù)組，并養(yǎng)成了在程序結束時釋放動態(tài)二維數(shù)組內存的習慣。4.明白了歐拉回路屬于歐拉路的一種特殊情況，之前一直沒有搞清這兩者之間的關系。在判斷是歐拉圖還是半歐拉圖時，首先判斷是不是連通圖，然后判斷是否只存在零個或者兩個奇數(shù)度結點，有兩個則是半歐拉圖，零個則是歐拉圖。5.輸出歐