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

1、離散數(shù)學(xué)實(shí)驗(yàn)報(bào)告（2015 / 2016學(xué)年 第 一 學(xué)期）題 目：圖的隨機(jī)生成及歐拉（回）路的確定專業(yè)信息安全學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師指導(dǎo)單位計(jì)算機(jī)學(xué)除計(jì)算機(jī)科學(xué)與技術(shù)系日期2015年12月29日?qǐng)D的隨機(jī)生成及歐拉（回）路的確定一、實(shí)驗(yàn)內(nèi)容和要求內(nèi)容：編程隨機(jī)生成n個(gè)結(jié)點(diǎn)的無向圖并能進(jìn)行（半）歐拉圖的判定，若是則給出歐 拉（回）路。要求：對(duì)給定n個(gè)結(jié)點(diǎn)，隨機(jī)生成鄰接矩陣以確定某無向簡(jiǎn)單圖并進(jìn)行歐拉圖和半歐 拉圖的判定，若符合則給出至少一條歐拉回路或歐拉路。二、實(shí)驗(yàn)?zāi)康膶?duì)給定n個(gè)結(jié)點(diǎn)，隨機(jī)生成鄰接矩陣以確定某無向簡(jiǎn)單圖并進(jìn)行歐拉圖和半歐拉圖的判定，若符合則給出至少一條歐拉回路或歐拉路三、實(shí)驗(yàn)任

2、務(wù)1、輸入結(jié)點(diǎn)個(gè)數(shù)據(jù)生成隨機(jī)圖2、進(jìn)行(半)歐拉圖的判定3、若是則給出歐拉(回)路。四、實(shí)驗(yàn)內(nèi)容#include #include #include using namespace std;class eulerpublic:euler(int num);公有的深度優(yōu)先搜索函數(shù)/輸入邊/打印鄰接矩陣/打印可達(dá)性矩陣/warshall算法求可認(rèn)性矩陣/ /判斷圖是否連通/判斷圖是歐粒圖壞是半歐粒圖/ /私有的深度優(yōu)先搜索函數(shù)euler();void dfs(int begin);void inputedge();void printam();void printrm();void warshal

3、l();bool isconnected();int iseorse();bool iseuler;private:void dfs(int u,int v,bool *visited);int n;int *a;/定義動(dòng)態(tài)二維數(shù)組int *p;定義可1 大件矩陣int *b;；euler二euler(int num)iseuler=false;n=num;int i,j；a=new int*n;for(i=0;in;i+)ai=new intn;for(j=0;jn;j+)a皿=0；p=new int*n;for(i=0;in;i+)pi=new intn;for(j=0;jn;j+)p皿=

4、0；b=new intn;for(i=0;in;i+)bi=0；euler:euler()/ 析構(gòu)函數(shù)int i;for(i=0;in;i+) delete ai;delete a;for(i=0;in;i+) delete pi;delete p;delete b;void euler:inputedge()srand(unsigned)time(null);for(int i = 0; i n; i+)for(int j = i + 1; j n; j+)存儲(chǔ)每個(gè)結(jié)點(diǎn)的度數(shù)/構(gòu)造函數(shù)隨機(jī)牛成無向圖aij = 0+rand()%2; aji=aij;for(int ii=o;iin;ii+)

5、(for(intjj=0;jjn;jj+)(if(aiijj=1)(p間皿=1；pdjii=1；)void euler:printam()(cout隨機(jī)生成的圖為：endl;for(int i=0;in;i+)(for(int j=o;jn;j+) coutaidcoutendl;)void euler: :warshall()(for(int i=0;in;i+)for(int j=o;jn;j+)if(pdi=1) (for(int k=o;k0) )void euler:printrm()(cout可達(dá)性矩陣：endl;for(int i=0;in;i+)(for(int j=o;jn;

6、j+) coutpijcoutendl;bool euler:isconnected()int i,j;bool flag=true;for(i=0;in;i+)for(j=0;jn;j+) if(pij=0) flag=false; break;if(!flag) break;/ /flag標(biāo),己是否連通如果可達(dá)性矩陣中有一個(gè)元素為 0,/就跳出循環(huán)，表示該圖不連通if(!flag)cout該圖不是連通的;elsefor(i=0;in;i+) for(j=i;jn；j+) if(aij=1&i!=j) bi+；bj+； /return flag;int euler:iseorse()int

7、i,count=0,begin=-1;cout每個(gè)結(jié)點(diǎn)的度數(shù)：endl;for(i=0;in;i+)couti:biendl;for(i=0;in;i+) /計(jì)算奇數(shù)結(jié)點(diǎn)的個(gè)數(shù) if(bi%2!=0)count+;begin=i; /初始化開始結(jié)點(diǎn)，存在奇數(shù)結(jié)點(diǎn)，則將其中一個(gè)作為開始點(diǎn)if(begin=-1) /不存在奇數(shù)結(jié)點(diǎn)則將 0作為起始點(diǎn) begin=0;if(count=2)cout該圖是半歐拉圖endl;iseuler=true; /iseuler 標(biāo)記是否是(半)歐拉圖 else if(count=0) cout該圖是歐拉圖endl;iseuler=true;return begi

8、n;void euler:dfs(int begin)int i,j；bool *visited=new bool*n; / 二維數(shù)組,己錄每條邊是否被訪問過for(i=0;in;i+)/ 初始化 visitedi=new booln;for(j=0;jn;j+)if(aij=1)visitedij=false;elsevisitedij=true;for(j=0;jn;j+)if(!visitedbeginj)dfs(begin,j,visited);coutbegin;for(i=0;in;i+) delete visitedi; / 釋放內(nèi)存 delete 口visited;void e

9、uler二dfs(int u,int v,bool *visited)if(!visiteduv) / 米”斷功 是否訪問過visiteduv=true;visitedvu=true; / 標(biāo)記被訪問for(int i=0;in;i+)dfs(v,i,visited);coutv ;/ 輸出結(jié)點(diǎn)int main()int n,m,begin;bool flag;coutn;euler euler(n);euler.inputedge();euler.printam();euler.warshall();euler.printrm();flag=euler.isconnected();if(fl

10、ag) begin=euler.iseorse();if(euler.iseuler) cout具體路彳空為: euler.dfs(begin);coutendl;return 0;五、測(cè)試數(shù)據(jù)及其結(jié)果分析輸入結(jié)點(diǎn)個(gè)數(shù)：3 隨機(jī)生成的圖為 0 0 0q 0 00 0 0可達(dá)性矩陣:0 0 00 0 00 0 0該圖不是連通的process exited after 30 01 seconds with return value 0 請(qǐng)按任意鍵繼續(xù).輸入結(jié)點(diǎn)個(gè)數(shù)：2 隨機(jī)生成的圖為:0 00 0可達(dá)性矩陣：0 03 0該圖不是連通的 輸入結(jié)點(diǎn)個(gè)數(shù)：3 隨機(jī)生成的圖為：0 1 11 0 11 1

11、0可達(dá)性矩陣：1 1 11 1 11 1 1每個(gè)結(jié)點(diǎn)的度數(shù)：0:21:22-2核圖是歐拉圖具體路徑為：0 2 10drocess exited after 9.256 seconds with return value 0 清按任意鍵繼續(xù). .輸入結(jié)點(diǎn)個(gè)數(shù)：5 嵇機(jī)生底的函為：0 0 110 0 0 0 1 0 10 0 10 1110 10 0 0 10 可達(dá)性矩陣： 11111 11111 11111 11111 11111 摩個(gè)結(jié)點(diǎn)的度數(shù)：0:21:1 n. n b 44:1該圖是半歐拉圖具體路徑為：1 3 2 0 3 4輸入結(jié)點(diǎn)個(gè)數(shù)：6 隨機(jī)生成的圖為: 0 0 0 1 1 0 0 0

12、 0 1 0 1 0 0 0 0 1 1 110 0 11 10 110 1 0 11110 可達(dá)性矩陣； 111111 111111 111111 111111 111111 111111 每個(gè)結(jié)點(diǎn)的度數(shù)工 0:2 1:2 2:2 3:4 4:45 - 4 核圖是歐拉圖具體路徑為工0453425130隨機(jī)生成的圖為工 0 10 0 0 10 0 11 0 0 0 1 1 0 110 0 0 110 0 可達(dá)性矩陣； 11111 11111 11111 11111 11111每個(gè)結(jié)點(diǎn)的度數(shù), 0:1 1:3 2:2 3:2 4：2成圖是半歐拉圖具體路徑為：0 1 1 4 2 3 1六、調(diào)試過程中的問題可達(dá)性矩陣無法正確計(jì)算，調(diào)試后發(fā)現(xiàn)是算法中未正確定義循環(huán)變量七、程序設(shè)計(jì)總結(jié)1 .掌握了與離散數(shù)學(xué)理論相關(guān)的編程實(shí)現(xiàn)思想和方法，掌握了歐拉圖和半歐拉圖的判2 .利用鄰接矩陣表示存在的邊，通過 warshall算法求出無向圖的可達(dá)性矩陣，如果 是連通的話，那么可達(dá)性矩陣中每一個(gè)元素都應(yīng)該為1,否則存在元素為003 .多次利用動(dòng)態(tài)二維數(shù)組，并養(yǎng)成了在程序結(jié)束時(shí)釋放動(dòng)態(tài)二維數(shù)組內(nèi)存的習(xí)慣。4 .明白了歐拉回路屬于歐拉路的一種特殊情況，之前一直沒有搞清這兩者之間的關(guān) 系。在判斷是歐拉圖還是半歐拉圖時(shí)，首先判斷是不是連通圖，然后判斷是否只存在零個(gè) 或者兩個(gè)奇數(shù)度結(jié)點(diǎn)，有兩個(gè)則是半歐拉