1、<p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2012 ～2013 學(xué)年第 2 學(xué)期</p><p>　　2013 年 3月</p><p><b>　　題目：</b><

2、;/p><p>　　歐拉回路是指不令筆離開紙面，可畫過(guò)圖中每條邊僅一次，且可以回到起點(diǎn)的一條回路?，F(xiàn)給定一個(gè)圖，問(wèn)是否存在歐拉回路？</p><p>　　一．問(wèn)題分析和任務(wù)定義：</p><p>　　題目要求判斷一個(gè)給定的圖中是否存在歐拉回路。由歐拉圖的定義，當(dāng)一個(gè)圖存在歐拉回路時(shí)，該圖稱為歐拉圖。題目問(wèn)是否存在歐拉回路即等價(jià)于問(wèn)給定的圖是否為歐拉圖。所以，證明給定圖是

3、歐拉圖就說(shuō)明該圖存在歐拉回路，否則不存在歐拉回路。根據(jù)高等教育出版社出版屈婉玲、耿素云、張立昂主編的《離散數(shù)學(xué)》P.296定理15.1可知：無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖且沒(méi)有奇度頂點(diǎn)。要證明一個(gè)給定的圖是否為歐拉圖，證明給定的圖是連通圖且沒(méi)有奇度頂點(diǎn)即可。所以，解決題目中的問(wèn)題就轉(zhuǎn)化為證明給定圖是否是連通圖且沒(méi)有奇度頂點(diǎn)。</p><p>　　首先要確定一給定的圖是否為連通圖。這里我們可以通過(guò)圖的深度優(yōu)先搜

4、索遍歷確定。從任意頂點(diǎn)出發(fā)，如果能深度優(yōu)先遍歷到所有的頂點(diǎn)就說(shuō)明圖中所有的頂點(diǎn)都是連圖的即為連通圖。</p><p>　　然后再確定給定的圖是否沒(méi)有奇度頂點(diǎn)。我們可以以鄰接矩陣的形式存儲(chǔ)給定的圖，對(duì)鄰接矩陣的每行分別行進(jìn)行掃描，記錄每個(gè)頂點(diǎn)的度數(shù)，當(dāng)每行掃描完后判斷該頂點(diǎn)的度數(shù)是否為奇數(shù)，存在奇度頂點(diǎn)直接結(jié)束掃描，說(shuō)明存在奇度頂點(diǎn)，給定圖不是歐拉圖。即不存在歐拉回路。否則繼續(xù)掃描，當(dāng)掃描完所有的行沒(méi)有發(fā)現(xiàn)奇度頂點(diǎn)

5、，即說(shuō)明給定圖沒(méi)有奇度頂點(diǎn)。</p><p>　　當(dāng)上述兩個(gè)問(wèn)題都確定以后根據(jù)定理，當(dāng)且僅當(dāng)給定圖為連通圖且沒(méi)有奇度頂點(diǎn)時(shí)給定的圖為歐拉圖。由此可確定，給定的圖是否存在歐拉回路。</p><p>　　二．?dāng)?shù)據(jù)結(jié)構(gòu)的選擇與概要設(shè)計(jì)：</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)的選擇：</b></p><p>　　圖在我們所學(xué)的數(shù)

6、據(jù)結(jié)構(gòu)與算法課程中有四種存儲(chǔ)方式：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。本問(wèn)題比較簡(jiǎn)單，選用鄰接矩陣或鄰接矩陣就足夠了。在本課程設(shè)計(jì)中需要判斷是否有奇度頂點(diǎn)和是否為連通圖，用用鄰接表和鄰接矩陣在時(shí)間繁雜度沒(méi)有什么大的差別，在空間復(fù)雜度上，因?yàn)楸绢}是無(wú)向圖，如果如果用鄰接表，儲(chǔ)存一條邊要儲(chǔ)存兩次，存儲(chǔ)指針比int型的空間消耗大，在圖不是很大的情況下，鄰接矩陣的空間復(fù)雜度要小。同時(shí)選用鄰接矩陣很容易得到圖中個(gè)頂點(diǎn)的度數(shù)。因?yàn)轫旤c(diǎn)只要求編號(hào)

7、這一信息，所以就沒(méi)有用結(jié)構(gòu)體存儲(chǔ)頂點(diǎn)信息，圖用鄰接矩陣要用結(jié)構(gòu)體存儲(chǔ)。結(jié)構(gòu)體定義如下：</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int n;//頂點(diǎn)個(gè)數(shù)</p><p>　　int e;//邊的條數(shù)</p><p>　　int

8、vexs[MAX_VERTEX_NUM];//一維數(shù)組儲(chǔ)存頂點(diǎn)</p><p>　　int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數(shù)組儲(chǔ)存邊</p><p>　　}MGraph;//圖</p><p><b>　　2.概要設(shè)計(jì)</b></p><p>　　首先將圖轉(zhuǎn)換為鄰接矩

9、陣存儲(chǔ)起來(lái)，然后鄰接矩陣的每一行進(jìn)行搜索得圖中到每個(gè)頂點(diǎn)的度數(shù)，如果有奇度頂點(diǎn)，輸出：不存在歐拉回路，即可結(jié)束程序。否則繼續(xù)判斷給定的圖是否為連通圖，如果是連通圖輸出：存在歐拉回路；否則輸出：不存在歐拉回路。結(jié)束程序。</p><p>　　三．詳細(xì)設(shè)計(jì)和編碼：</p><p>　　1.將圖轉(zhuǎn)化為鄰接矩陣存儲(chǔ)：</p><p>　　先輸入圖中頂點(diǎn)個(gè)個(gè)數(shù)和邊的條數(shù)，對(duì)所

10、有可能存在的邊初始化為0，再依次輸入邊的信息，即如果頂點(diǎn)1,2存在相連的邊，輸入1 2 （1,2為自動(dòng)給頂點(diǎn)分配的編碼）。將邊1,2的信息改為1。用函數(shù)MGraph *creat_MGraph();完成，返回鄰接矩陣的首地址即可。</p><p>　　MGraph *creat_MGraph()//建立鄰接矩陣</p><p><b>　　{</b></p>

11、;<p>　　int i,j,k,n,e;</p><p>　　MGraph *mg=malloc(sizeof(MGraph));</p><p>　　printf("請(qǐng)輸入頂點(diǎn)的個(gè)數(shù)：");</p><p>　　scanf("%d",&n);</p><p>　　printf(

12、"請(qǐng)輸入邊的條數(shù)：");</p><p>　　scanf("%d",&e);</p><p><b>　　mg->n=n;</b></p><p><b>　　mg->e=e;</b></p><p>　　getchar();</p&

13、gt;<p>　　for(i=1;i<=n;i++)</p><p>　　for(j=1;j<=n;j++)</p><p>　　mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊</p><p>　　printf("請(qǐng)輸入邊的信息:\n");</p><p>　　for(i

14、=1;i<=e;i++)</p><p><b>　　{</b></p><p>　　scanf("%d%d",&j,&k);</p><p>　　mg->edges[j][k]=1;mg->edges[k][j]=1;//標(biāo)記存在的邊</p><p><b&g

15、t;　　}</b></p><p>　　return mg;//返回鄰接矩陣的首地址</p><p><b>　　}</b></p><p>　　2.搜索有沒(méi)有奇度頂點(diǎn)：</p><p>　　對(duì)鄰接矩陣的每一行進(jìn)行搜索，用num記錄頂點(diǎn)的度數(shù)（每次對(duì)新的頂點(diǎn)記錄前都將num置為0）。為了排除頂點(diǎn)自身環(huán)對(duì)判斷的

16、影響，當(dāng)遇到邊的兩頂點(diǎn)相同，忽略不計(jì)，這樣不會(huì)對(duì)結(jié)果產(chǎn)生影響。如果搜索到奇度頂點(diǎn)則結(jié)束int Euleriancycle(MGraph *mg);函數(shù)，返回0，搜索完成且沒(méi)有發(fā)現(xiàn)奇度頂點(diǎn)則返回1.</p><p>　　int Euleriancycle(MGraph *mg)//判斷是否存在歐拉回路</p><p><b>　　{</b></p><

17、;p>　　int i,j,num;</p><p>　　for(i=1;i<=mg->n;i++)//從第一個(gè)頂點(diǎn)開始，判斷頂點(diǎn)的度數(shù)</p><p><b>　　{</b></p><p>　　num=0;//初始化每個(gè)頂點(diǎn)的度數(shù)為0</p><p>　　for(j=1;j<=mg->n;

18、j++)</p><p><b>　　{</b></p><p>　　if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點(diǎn)i到j(luò)的邊存在度數(shù)加1</p><p>　　num=num+1;</p><p><b>　　}</b></p>&l

19、t;p>　　if(num%2==1)//如果有哪個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0</p><p>　　return 0;</p><p><b>　　}</b></p><p>　　return 1;//當(dāng)所有的頂點(diǎn)都判斷完成還沒(méi)有退出本函數(shù)說(shuō)明所有頂點(diǎn)度數(shù)均為偶數(shù)，返回1</p><p><b&g

20、t;　　}</b></p><p>　　3. 判斷給定的圖是否為連通圖：</p><p>　　本程序的深度優(yōu)先遍歷是一個(gè)遞歸的過(guò)程。其中visited[MAX_VERTEX_NUM]是一個(gè)輔助的全局變量，初始值均為0.表示該頂點(diǎn)沒(méi)有被訪問(wèn)。訪問(wèn)后用1表示。在深度優(yōu)先搜索時(shí)。我們需要調(diào)用dfs_trave()函數(shù)。在dfs_trave()中，針對(duì)每個(gè)沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)調(diào)用dfs(

21、)函數(shù)，它是一個(gè)遞歸函數(shù)，完成從該頂點(diǎn)開始的深度優(yōu)先搜索。如果圖是一個(gè)連通圖，那么完成對(duì)visited數(shù)組的初始化后，在dfs_trave()中只需調(diào)用dfs()函數(shù)一次即可完成對(duì)圖的遍歷。當(dāng)圖不是一個(gè)連通圖時(shí)，則在dfs_trave()中需要針對(duì)每個(gè)連通分量分別調(diào)用dfs()函數(shù)。根據(jù)dfs()函數(shù)被調(diào)用的次數(shù)就可以判斷給定的圖是否為連通圖。如果dfs()函數(shù)被調(diào)用一次則給定的圖是連通圖，否則不是連通圖。</p><

22、;p>　　int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷</p><p><b>　　{</b></p><p>　　int i,m=0;</p><p>　　for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)</p><p>　　vi

23、sited[i]=0;</p><p>　　for(i=1;i<=mg->n;i++)</p><p>　　if(visited[i]==0)//對(duì)沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)，調(diào)用深度優(yōu)先搜索函數(shù)</p><p><b>　　{</b></p><p>　　dfs(mg,i);//深度優(yōu)先搜索</p>&

24、lt;p>　　m=m+1;//如果是非連通圖，要調(diào)用1次以上，m用來(lái)記錄調(diào)用dfs函數(shù)的次數(shù)</p><p><b>　　}</b></p><p>　　return m;//返回調(diào)用dfs函數(shù)的次數(shù)</p><p><b>　　}</b></p><p>　　void dfs(MGraph

25、*mg,int i)//深度優(yōu)先搜索</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　visited[i]=1;//訪問(wèn)該頂點(diǎn)</p><p>　　for(j=1;j<=mg->n;j++)</p><p&

26、gt;　　if((visited[j]==0)&&(mg->edges[i][j]==1))//當(dāng)頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)并且兩頂點(diǎn)存在邊</p><p>　　dfs(mg,j);//對(duì)該頂點(diǎn)深度優(yōu)先搜索</p><p><b>　　}</b></p><p>　　4.根據(jù)上述2,3可知，必須為連通圖且沒(méi)有奇度頂點(diǎn)才是歐拉圖即存在

27、歐拉回路。</p><p>　　5.流程圖如下（圖：1）：</p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p&

28、gt;<p><b>　　圖：1流程圖</b></p><p><b>　　四．上機(jī)調(diào)試過(guò)程：</b></p><p>　　本次實(shí)驗(yàn)中也遇到了一些小問(wèn)題，通過(guò)在適當(dāng)?shù)奈恢眉右恍﹑rintf語(yǔ)句即可確定出現(xiàn)問(wèn)題的語(yǔ)句大概的位置。加以分析、修改即可。</p><p>　　在本次課程設(shè)計(jì)的第三組數(shù)據(jù)的測(cè)試時(shí)出現(xiàn)了不

29、存在歐拉圖的錯(cuò)誤結(jié)果，仔細(xì)分析可知，在（2,2）鄰接矩陣的對(duì)角線上，所以該點(diǎn)的度數(shù)在計(jì)算的時(shí)候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點(diǎn)i到j(luò)的邊存在度數(shù)加1 的判斷中增加了一個(gè)判斷，當(dāng)該點(diǎn)存在環(huán)，則在度數(shù)的計(jì)數(shù)時(shí)忽略不計(jì)，這樣不會(huì)印象該點(diǎn)度數(shù)奇偶性的變化。這樣就很好的解決了，存在環(huán)對(duì)判斷結(jié)果的印象的問(wèn)題。</p><p>　　通過(guò)本次課程

30、設(shè)計(jì)讓我更加深刻的體會(huì)到調(diào)試程序需要平心靜氣，仔細(xì)分析、研究。要有一個(gè)嚴(yán)謹(jǐn)?shù)膽B(tài)度，這樣才能高效率的寫出優(yōu)質(zhì)的代碼。</p><p>　　五．測(cè)試結(jié)果與分析：</p><p><b>　　測(cè)試數(shù)據(jù)的選擇：</b></p><p>　　在測(cè)試中考慮到多種情況使用了多組數(shù)據(jù)，分別根據(jù)是否為連通圖、是否沒(méi)有奇度頂點(diǎn)設(shè)計(jì)了一下四組數(shù)據(jù)。第一組數(shù)據(jù)為連通圖

31、且沒(méi)有奇度頂點(diǎn)，第二組數(shù)據(jù)為連通圖且有奇度頂點(diǎn)，第三組數(shù)據(jù)為連通圖、沒(méi)有奇度頂點(diǎn)且有環(huán)，第四組數(shù)據(jù)為非連通圖且有奇度頂點(diǎn)，第五組數(shù)據(jù)為非連通圖且沒(méi)有奇度頂點(diǎn)。</p><p>　　每組數(shù)據(jù)進(jìn)行多次測(cè)試。</p><p><b>　　測(cè)試數(shù)據(jù)1：</b></p><p><b>　　3</b></p><

32、p><b>　　3</b></p><p><b>　　1 2</b></p><p><b>　　1 3</b></p><p><b>　　2 3</b></p><p><b>　　測(cè)試結(jié)果：</b></p>

33、<p>　　結(jié)果分析：測(cè)試數(shù)據(jù)表示一個(gè)3個(gè)頂點(diǎn)，3條邊的圖，頂點(diǎn)兩兩相連。如下:2-1所示：</p><p>　　圖：2-1 測(cè)試1</p><p>　　存在歐拉回路。測(cè)試結(jié)果正確。</p><p><b>　　測(cè)試數(shù)據(jù)2：</b></p><p><b>　　3</b></p&

34、gt;<p><b>　　3</b></p><p><b>　　3 2</b></p><p><b>　　1 2</b></p><p><b>　　2 3</b></p><p><b>　　測(cè)試結(jié)果：</b>&l

35、t;/p><p>　　結(jié)果分析：測(cè)試數(shù)據(jù)表示一個(gè)3個(gè)頂點(diǎn)，3條邊的圖，1,、2相連，2、3相連。如下圖2-2所示：</p><p>　　圖：2-2 測(cè)試2</p><p>　　不存在歐拉回路。測(cè)試結(jié)果正確。</p><p><b>　　測(cè)試數(shù)據(jù):3：</b></p><p><b>　　4

36、</b></p><p><b>　　5</b></p><p><b>　　1 2</b></p><p><b>　　1 3</b></p><p><b>　　2 4</b></p><p><b>　　

37、3 4</b></p><p><b>　　2 2</b></p><p><b>　　測(cè)試結(jié)果： </b></p><p>　　結(jié)果分析：測(cè)試數(shù)據(jù)表示一個(gè)4個(gè)頂點(diǎn)，5條邊的圖，1、2相連，1、3相連,2、4相連,3、4相連，2、2相連。如下圖2-3所示：</p><p><b&g

38、t;　　圖：2-3 測(cè)試3</b></p><p>　　存在歐拉回路。測(cè)試結(jié)果正確。</p><p><b>　　測(cè)試數(shù)據(jù)4：</b></p><p><b>　　5</b></p><p><b>　　4</b></p><p><b

39、>　　1 2</b></p><p><b>　　3 4 </b></p><p><b>　　4 5</b></p><p><b>　　3 5</b></p><p><b>　　測(cè)試結(jié)果：</b></p><p&

40、gt;　　結(jié)果分析：測(cè)試數(shù)據(jù)表示一個(gè)5個(gè)頂點(diǎn)，4條邊的圖，1、2相連，3、4相連,4、5相連,3、5相連。如下:圖2-4所示：</p><p>　　不存在歐拉回路。測(cè)試結(jié)果正確。圖：2-4 測(cè)試4</p><p><b>　　測(cè)試數(shù)據(jù)5：</b></p><p><b>　　6</b></p><p

41、><b>　　6</b></p><p><b>　　1 2 </b></p><p><b>　　1 3</b></p><p><b>　　2 3</b></p><p><b>　　4 5</b></p>&

42、lt;p><b>　　4 6</b></p><p><b>　　5 6</b></p><p><b>　　測(cè)試結(jié)果：</b></p><p>　　結(jié)果分析：測(cè)試數(shù)據(jù)表示一個(gè)6個(gè)頂點(diǎn)，6條邊的圖，1、2相連，1、3相連,2、3相連,4、5相連，4、6相連，5、6相連。如下圖2-5所示：<

43、/p><p><b>　　圖：2-5</b></p><p>　　不存在歐拉回路。測(cè)試結(jié)果正確。</p><p>　　測(cè)試結(jié)果總結(jié)：通過(guò)對(duì)多種情況設(shè)計(jì)了多組數(shù)據(jù)多次測(cè)試如上，結(jié)果都得到了真確的結(jié)論。說(shuō)明程序符合題目的要求，達(dá)到了實(shí)驗(yàn)的目的。</p><p><b>　　六．用戶使用說(shuō)明：</b><

44、/p><p>　　首先本程序中的所有頂點(diǎn)編號(hào)為1-N的整數(shù)。(0<N<1000)</p><p>　　先輸入圖頂點(diǎn)的個(gè)數(shù)要求為一個(gè)正整數(shù)n，然后輸入圖所有邊的條數(shù)要求為正整數(shù)e，再圖邊數(shù)行整形數(shù)，每行兩個(gè)數(shù)（用空格相隔）表示一條邊所連接的兩個(gè)頂點(diǎn)編號(hào)。輸出結(jié)果即為題目的解。</p><p><b>　　七．參考文獻(xiàn)：</b></p

45、><p>　　[1] 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：高等教育出版社，2007年6月第1版</p><p>　　[2] 屈婉玲，耿素云，張立昂. 離散數(shù)學(xué). 北京：高等教育出版社，2008年3月第1版</p><p><b>　　八．附錄：</b></p><p>　　#include<stdio.h>&

46、lt;/p><p>　　#include<stdlib.h></p><p>　　#include<malloc.h></p><p>　　#define MAX_VERTEX_NUM 1000//頂點(diǎn)的最大個(gè)數(shù)</p><p>　　typedef struct</p><p><b>　

47、　{</b></p><p>　　int n;//頂點(diǎn)個(gè)數(shù)</p><p>　　int e;//邊的條數(shù)</p><p>　　int vexs[MAX_VERTEX_NUM];//一維數(shù)組儲(chǔ)存頂點(diǎn)</p><p>　　int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數(shù)組儲(chǔ)存邊</p

48、><p>　　}MGraph;//圖</p><p>　　int visited[MAX_VERTEX_NUM];//全局變量。在對(duì)頂點(diǎn)進(jìn)行深度優(yōu)先搜索遍歷時(shí)的輔助變量數(shù)組</p><p>　　int Euleriancycle(MGraph *mg);//判斷頂點(diǎn)的度數(shù)是否全為偶數(shù)，有奇數(shù)時(shí)輸出0，全為偶數(shù)時(shí)輸出1</p><p>　　MGra

49、ph *creat_MGraph();//將圖轉(zhuǎn)化為鄰接矩陣儲(chǔ)存起來(lái)，返回鄰接矩陣的首地址</p><p>　　int dfs_trave(MGraph *mg);//深度優(yōu)先搜索遍歷</p><p>　　void dfs(MGraph *mg,int i);//深度優(yōu)先搜索</p><p>　　void main()</p><p>&l

50、t;b>　　{</b></p><p>　　int num,m;//num用來(lái)接收頂點(diǎn)度數(shù)判斷的結(jié)果，m用來(lái)接收?qǐng)D是否為連通圖的結(jié)果</p><p>　　MGraph *mg;</p><p>　　mg=creat_MGraph();//建立鄰接矩陣</p><p>　　num=Euleriancycle(mg);//判斷頂

51、點(diǎn)的度數(shù)是否全為偶數(shù)。全為偶數(shù)時(shí)num=1；否則num=0</p><p>　　if(num!=1)</p><p><b>　　{</b></p><p>　　printf("不存在歐拉圖！\n");</p><p>　　getchar();</p><p><b>

52、;　　exit(0);</b></p><p><b>　　}</b></p><p>　　m=dfs_trave(mg);//判斷圖是否為連通圖</p><p><b>　　if(m!=1)</b></p><p>　　printf("不存在歐拉圖！\n");<

53、;/p><p><b>　　else</b></p><p>　　printf("存在歐拉圖！\n");</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p>　　MGraph *c

54、reat_MGraph()//建立鄰接矩陣</p><p><b>　　{</b></p><p>　　int i,j,k,n,e;</p><p>　　MGraph *mg=malloc(sizeof(MGraph));</p><p>　　printf("請(qǐng)輸入頂點(diǎn)的個(gè)數(shù)：");</p>

55、;<p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸入邊的條數(shù)：");</p><p>　　scanf("%d",&e);</p><p><b>　　mg->n=n;</b></p><p>

56、;<b>　　mg->e=e;</b></p><p>　　getchar();</p><p>　　for(i=1;i<=n;i++)</p><p>　　for(j=1;j<=n;j++)</p><p>　　mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊</p>

57、;<p>　　printf("請(qǐng)輸入邊的信息:\n");</p><p>　　for(i=1;i<=e;i++)</p><p><b>　　{</b></p><p>　　scanf("%d%d",&j,&k);</p><p>　　mg-&g

58、t;edges[j][k]=1;mg->edges[k][j]=1;//標(biāo)記存在的邊</p><p><b>　　}</b></p><p>　　return mg;//返回鄰接矩陣的首地址</p><p><b>　　}</b></p><p>　　int Euleriancycle(MGr

59、aph *mg)//判斷是否存在歐拉回路</p><p><b>　　{</b></p><p>　　int i,j,num;</p><p>　　for(i=1;i<=mg->n;i++)//從第一個(gè)頂點(diǎn)開始，判斷頂點(diǎn)的度數(shù)</p><p><b>　　{</b></p>

60、<p>　　num=0;//初始化每個(gè)頂點(diǎn)的度數(shù)為0</p><p>　　for(j=1;j<=mg->n;j++)</p><p><b>　　{</b></p><p>　　If((mg->edges[i][j]!=0)&&(i!=j))//如果頂點(diǎn)i到j(luò)的邊存在度數(shù)加1</p>

61、<p>　　num=num+1;</p><p><b>　　}</b></p><p>　　if(num%2==1)//如果有哪個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0</p><p>　　return 0;</p><p><b>　　}</b></p><p&g

62、t;　　return 1;//當(dāng)所有的頂點(diǎn)都判斷完成還沒(méi)有退出本函數(shù)說(shuō)明所有頂點(diǎn)度數(shù)均為偶數(shù)，返回1</p><p><b>　　}</b></p><p>　　int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷</p><p><b>　　{</b></p><p>　　in

63、t i,m=0;</p><p>　　for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)</p><p>　　visited[i]=0;</p><p>　　for(i=1;i<=mg->n;i++)</p><p>　　if(visited[i]==0)//對(duì)沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)

64、，調(diào)用深度優(yōu)先搜索函數(shù)</p><p><b>　　{</b></p><p>　　dfs(mg,i);//深度優(yōu)先搜索</p><p>　　m=m+1;//如果是非連通圖，要調(diào)用1次以上，m用來(lái)記錄調(diào)用dfs函數(shù)的次數(shù)</p><p><b>　　}</b></p><p>

65、;　　return m;//返回調(diào)用dfs函數(shù)的次數(shù)</p><p><b>　　}</b></p><p>　　void dfs(MGraph *mg,int i)//深度優(yōu)先搜索</p><p><b>　　{</b></p><p><b>　　int j;</b><

66、;/p><p>　　visited[i]=1;//訪問(wèn)該頂點(diǎn)</p><p>　　for(j=1;j<=mg->n;j++)</p><p>　　if((visited[j]==0)&&(mg->edges[i][j]==1))//當(dāng)頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)并且兩頂點(diǎn)存在邊</p><p>　　dfs(mg,j);//對(duì)