離散數(shù)學實驗四

PAGE實驗報告（2014/2015學年第一學期）課程名稱離散數(shù)學實驗名稱圖的隨機生成及歐拉（回）路的確定實驗時間2014年12月12日指導單位南京郵電大學指導教師羅衛(wèi)蘭學生姓名沈一州班級學號B12040920學院(系)計算機軟件學院專業(yè)NIIT（軟嵌）5-實驗報告實驗名稱圖的隨機生成及歐拉（回）路的確定指導教師羅衛(wèi)蘭實驗類型驗證型實驗學時4實驗時間12.12實驗目的和要求內(nèi)容：編程隨機生成n個結(jié)點的無向圖并能進行（半）歐拉圖的判定，若是則給出歐拉（回）路。要求：對給定n個結(jié)點，隨機生成鄰接矩陣以確定某無向簡單圖并進行歐拉圖和半歐拉圖的判定，若符合則給出至少一條歐拉回路或歐拉路。實驗環(huán)境(實驗設備)硬件：CPU：3.0Ghz內(nèi)存：1.00GB軟件：操作系統(tǒng)：WindowsXPSP3編程軟件：VisualC++6.0實驗原理及內(nèi)容總體思想：這次題目要求是根據(jù)隨機生成的圖求歐拉（回）路，先要隨機生成一個鄰接矩陣，然后判定是否是歐拉回路只要根據(jù)奇數(shù)度結(jié)點的個數(shù)。再用一個遞歸函數(shù)找出歐拉路。核心代碼：1、根據(jù)結(jié)點數(shù)生成鄰接矩陣： for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j)//同一個結(jié)點間沒有邊 a[i][j]=0; elseif(i>j)//邊沒有方向性 a[i][j]=a[j][i]; else{//隨機賦值，0代表沒有邊，1代表有邊 a[i][j]=rand()%2; } } cout<<"";//輸出該鄰接矩陣 for(i=0;i<n;i++){ cout<<""<<i+1; } cout<<endl; for(i=0;i<n;i++){ cout<<i+1; for(j=0;j<n;j++){ cout<<""<<a[i][j]; } cout<<endl; }2、根據(jù)奇數(shù)度結(jié)點數(shù)判定是否含有歐拉(回)路： odd=0; for(i=0;i<n;i++){ count=0; for(j=0;j<n;j++){ count+=a[i][j];//統(tǒng)計每個結(jié)點的度數(shù) } if(count%2==1) odd++;//若為奇數(shù)，則總數(shù)+1 } if(odd==0) cout<<"該圖沒有奇數(shù)度結(jié)點，具有歐拉回路，是歐拉圖。"<<endl; elseif(odd==2) cout<<"該圖有兩個奇數(shù)度結(jié)點，具有歐拉路，是半歐拉圖。"<<endl; else cout<<"該圖奇數(shù)度結(jié)點的個數(shù)為"<<odd<<"，所以不具有歐拉路。"<<endl;3、半歐拉圖中找出奇數(shù)度結(jié)點標號： flag1=flag2=-1;//分別代表兩個奇數(shù)度結(jié)點的標號 for(i=0;i<n;i++){ count=0; for(j=0;j<n;j++){ count+=a[i][j]; } if(count%2==1){ if(flag1==-1) flag1=i+1; else flag2=i+1; } }4、求歐拉(回)路：voidfind(intfound,inttime){ inti,j,flag; for(i=0;i<n;i++){ if(a[found][i]==1){ flag=0; for(j=0;j<time;j++){//表示是否已經(jīng)存在 if(b[j]==i){ flag=1;break; } } if(!flag){ b[time]=i; time++; if(time<exist){//如果還沒走完 find(i,time);//遞歸 } else{ return; } } } }}四、運行結(jié)果：首先是輸入結(jié)點數(shù)：然后隨機打印出鄰接矩陣：根據(jù)性質(zhì)判斷并求出歐拉圖：再試3次：實驗報告五、實驗小結(jié)這次題目要求是根據(jù)隨機生成的圖求歐拉（回）路，首先難點是如何隨機生成一個圖，這要考慮到3個細節(jié)：第1個是同一個結(jié)點之間沒有邊，第2個就是這是無向圖，一旦一個結(jié)點有了一條邊，對應的另一個結(jié)點也要有一條邊，第3個是要考慮到孤立結(jié)點。在此基礎上生成了鄰接矩陣，歐拉圖判斷就好弄多了，只要判斷奇數(shù)度結(jié)點的個數(shù)。然后再用遞歸函數(shù)找到一條可行路即可。通過這次實驗，加深了我對圖的相關(guān)知識的理解，也提高了我動手編程的能力。五、指導教師評語