數(shù)據(jù)結構與算法課程設計報告-wenkub.com
2025-04-11 04:41 本頁面
【正文】 amp。 visited[i]=1。i++) if(visited[i]==0)//對沒有訪問過的頂點，調用深度優(yōu)先搜索函數(shù) { dfs(mg,i)。i=mgn。 } if(num%2==1)//如果有哪個頂點的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0 return 0。j=mgn。 for(i=1。 mgedges[j][k]=1。i=e。j=n。 getchar()。 scanf(%d,amp。 printf(請輸入頂點的個數(shù)：)。 else printf(存在歐拉圖！\n)。 getchar()。 mg=creat_MGraph()。//將圖轉化為鄰接矩陣儲存起來，返回鄰接矩陣的首地址int dfs_trave(MGraph *mg)。//圖int visited[MAX_VERTEX_NUM]。//頂點個數(shù) int e。六．用戶使用說明：首先本程序中的所有頂點編號為1N的整數(shù)。如下圖25所示：541632 圖：25不存在歐拉回路。測試數(shù)據(jù)4：541 23 4 4 53 5測試結果：結果分析：測試數(shù)據(jù)表示一個5個頂點，4條邊的圖，2相連，4相連,5相連,5相連。測試結果正確。如下:21所示：132 圖：21 測試1存在歐拉回路。五．測試結果與分析：測試數(shù)據(jù)的選擇：在測試中考慮到多種情況使用了多組數(shù)據(jù)，分別根據(jù)是否為連通圖、是否沒有奇度頂點設計了一下四組數(shù)據(jù)。(i!=j))//如果頂點i到j的邊存在度數(shù)加1 的判斷中增加了一個判斷，當該點存在環(huán)，則在度數(shù)的計數(shù)時忽略不計，這樣不會印象該點度數(shù)奇偶性的變化。加以分析、修改即可。amp。 visited[i]=1。i++) if(visited[i]==0)//對沒有訪問過的頂點，調用深度優(yōu)先搜索函數(shù) { dfs(mg,i)。i=mgn。根據(jù)dfs()函數(shù)被調用的次數(shù)就可以判斷給定的圖是否為連通圖。我們需要調用dfs_trave()函數(shù)。//當所有的頂點都判斷完成還沒有退出本函數(shù)說明所有頂點度數(shù)均為偶數(shù)，返回1}3. 判斷給定的圖是否為連通圖：本程序的深度優(yōu)先遍歷是一個遞歸的過程。amp。i++)//從第一個頂點開始，判斷頂點的度數(shù) { num=0。如果搜索到奇度頂點則結束int Euleriancycle(MGraph *mg)。mgedges[k][j]=1。i++) { scanf(%d%d,amp。j++) mgedges[i][j]=0。 for(i=1。e)。 scanf(%d,amp。完成，返回鄰接矩陣的首地址即可。結束程序。//一維數(shù)組儲存頂點 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。因為頂點只要求編號這一信息，所以就沒有用結構體存儲頂點信息，圖用鄰接矩陣要用結構體存儲。二．數(shù)據(jù)結構的選擇與概要設計：1． 數(shù)據(jù)結構的選擇：圖在我們所學的數(shù)據(jù)結構與算法課程中有四種存儲方式：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。即不存在歐拉回路。這里我們可以通過圖的深度優(yōu)先搜索遍歷確定。根
公司管理相關推薦
鄂ICP備17016276號-1