離散實(shí)驗(yàn)報(bào)告四

1、一、實(shí)驗(yàn)?zāi)康呐袛嚯S機(jī)生成的鄰接矩陣是否為歐拉圖或歐拉半圖，若是，求取其歐拉回路或歐拉路。二、問題分析本實(shí)驗(yàn)的最終目的是要求取歐拉圖的歐拉回路或歐拉半圖的歐拉路，那么在這之前我們需要完成的是鄰接矩陣的生成，圖的連通性判別，如若連通，再判斷其是否為歐拉圖或歐拉半圖，最終求取歐拉回路或歐拉路。1.生成隨機(jī)矩陣定義數(shù)組二維數(shù)組l，用以存儲(chǔ)鄰接矩陣的信息。再定義結(jié)點(diǎn)數(shù)目n，從鍵盤鍵入之。根據(jù)n的大小，在嵌套的for循環(huán)中，每次循環(huán)都利用rand函數(shù)隨機(jī)生成某數(shù)并對(duì)2取余，將結(jié)果賦值給lij。當(dāng)然在for循環(huán)之前需要調(diào)用srand函數(shù)取計(jì)算機(jī)當(dāng)前時(shí)間作為種子，防止rand函數(shù)生成偽隨機(jī)數(shù)。2.判斷連通性考

2、慮到在上述步驟中已經(jīng)有圖的鄰接矩陣生成，可以考慮用可達(dá)性矩陣來判斷圖的連通性。這樣，問題的關(guān)鍵就變成了求取可達(dá)性矩陣的問題。為了不影響原鄰接矩陣信息，定義新二維數(shù)組p復(fù)制鄰接矩陣數(shù)據(jù)來進(jìn)行運(yùn)算操作，并定義二維數(shù)組s，初始化為全0，用來存儲(chǔ)最終可達(dá)性矩陣。具體操作應(yīng)為：首先將利用for循環(huán)將p與l相乘，結(jié)果存于p中；而后將p加上s，結(jié)果存于s中。再將以上步驟整體置于一個(gè)循環(huán)n次的for循環(huán)下。執(zhí)行完之后，檢查s，將非零值都修正為1，這樣我們可以得到可達(dá)性矩陣s。最后，遍歷檢查s中每個(gè)元素的值，如果發(fā)現(xiàn)有元素值為0，那么該圖不具有連通性；否則，該圖具有連通性，可以進(jìn)行下面步驟的判斷。3.判斷是否為

3、歐拉圖或歐拉半圖定義數(shù)組deg，用來存儲(chǔ)每個(gè)結(jié)點(diǎn)的度。依行檢查l，將第i行的值相加可得degi。再依據(jù)deg來判斷該圖是否為歐拉圖或歐拉半圖：如果每個(gè)結(jié)點(diǎn)的度均為偶數(shù)，該圖為歐拉圖；如果奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)為2，該圖為歐拉半圖；否則，兩者均不是。4.歐拉路或歐拉回路的求取對(duì)于歐拉路或歐拉回路的求取，我們依舊利用鄰接矩陣來求。（1）求取歐拉回路時(shí)，我們可以任意選擇起點(diǎn)開始。按行搜索鄰接矩陣，若果檢查第i行時(shí)發(fā)現(xiàn)lij非0，將其修正為0后，輸出i->j，搜索第j行，如此循環(huán)，可得歐拉回路。當(dāng)然在此之前我們需要求得每個(gè)結(jié)點(diǎn)的度數(shù)之和sum，來控制上述循環(huán)次數(shù)不超過sum/2，使得循環(huán)可以適時(shí)結(jié)束。（

4、2）在求取歐拉路時(shí)，只要控制循環(huán)起點(diǎn)為奇數(shù)度結(jié)點(diǎn)即可。其他步驟與上述求取歐拉回路步驟一致。三、具體程序?qū)崿F(xiàn)#include <iostream>#include <cstdlib>#include <ctime>using namespace std;int main()int n,l2020,p2020,s2020;int deg20;/用于存儲(chǔ)每個(gè)結(jié)點(diǎn)的度數(shù)int count1=0;/用于存儲(chǔ)奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)int start=0;srand(int)time(0);cout<<"請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù):"cin>>n;

5、for(int i=0;i<n;i+)for(int j=i;j<n;j+)if(i=j)lij=0;elselij=rand()%2;lji=lij;cout<<"隨機(jī)生成領(lǐng)接矩陣："<<endl;for(i=0;i<n;i+)degi=0;for(int j=0;j<n;j+)cout<<lij<<" "cout<<endl;/通過可達(dá)性矩陣判斷連通性for(i=0;i<n;i+)for(int j=0;j<n;j+)pij=lij;sij=0;for(i

6、nt y=0;y<n;y+) for(i=0;i<n;i+) for(int j=0;j<n;j+) sij+=pij; for(i=0;i<n;i+) for(int j=0;j<n;j+) for(int k=0;k<n;k+) pij+=pik*lkj; for(i=0;i<n;i+)for(int j=0;j<n;j+)if(sij!=0)sij=1;cout<<"可達(dá)性矩陣為:"<<endl;for(i=0;i<n;i+)for(int j=0;j<n;j+)cout<<

7、;sij<<" "cout<<endl;/歐拉（半）圖的判斷和歐拉（回）路的的求取int sum=0;for(i=0;i<n;i+)for(int j=0;j<n;j+)if(lij=1)degi+;for(i=0;i<n;i+)if(degi%2!=0)count1+;start=i;for(i=0;i<n;i+)sum=sum+degi;for(i=0;i<n;i+)for(int j=0;j<n;j+)if(sij=0)cout<<"此圖不連通"<<endl;cou

8、t<<"既不是歐拉圖也不是歐拉半圖"<<endl;return 0;int x=0;int j=100;cout<<"此圖連通"<<endl;if(count1=0)cout<<"是歐拉圖，歐拉回路如下："<<endl;for(i=0;x<sum/2;i=j)for(j=0;j<n;j+)if(lij=1)cout<<i+1<<"->"<<j+1<<endl;lij=0;lji=0;x+;break;else if(count1=2)cout<<"是歐拉半圖，歐拉路如下："<<endl;for(i=start;x<sum/2;i=j)for(j=0;j<n;j+)if(lij=1)cout<<i+1<<&qu