數(shù)據(jù)結(jié)構(gòu)與算法課程設計報告-免費閱讀
【正文】 j=mgn。 for(i=1。amp。//標記存在的邊 } return mg。//初始化鄰接矩陣表示的所有邊 printf(請輸入邊的信息:\n)。 mgn=n。}MGraph *creat_MGraph()//建立鄰接矩陣{ int i,j,k,n,e。//判斷頂點的度數(shù)是否全為偶數(shù)。在對頂點進行深度優(yōu)先搜索遍歷時的輔助變量數(shù)組int Euleriancycle(MGraph *mg)。輸出結(jié)果即為題目的解。測試結(jié)果正確。測試數(shù)據(jù)2：333 21 22 3測試結(jié)果： 結(jié)果分析：測試數(shù)據(jù)表示一個3個頂點，3條邊的圖，1,、2相連，3相連。通過本次課程設計讓我更加深刻的體會到調(diào)試程序需要平心靜氣，仔細分析、研究。//對該頂點深度優(yōu)先搜索},3可知，必須為連通圖且沒有奇度頂點才是歐拉圖即存在歐拉回路。//如果是非連通圖，要調(diào)用1次以上，m用來記錄調(diào)用dfs函數(shù)的次數(shù) } return m。int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷{ int i,m=0。訪問后用1表示。j=mgn。//返回鄰接矩陣的首地址}：對鄰接矩陣的每一行進行搜索，用num記錄頂點的度數(shù)（每次對新的頂點記錄前都將num置為0）。 for(i=1。 mge=e。 MGraph *mg=malloc(sizeof(MGraph))。//圖首先將圖轉(zhuǎn)換為鄰接矩陣存儲起來，然后鄰接矩陣的每一行進行搜索得圖中到每個頂點的度數(shù)，如果有奇度頂點，輸出：不存在歐拉回路，即可結(jié)束程序。在本課程設計中需要判斷是否有奇度頂點和是否為連通圖，用用鄰接表和鄰接矩陣在時間繁雜度沒有什么大的差別，在空間復雜度上，因為本題是無向圖，如果如果用鄰接表，儲存一條邊要儲存兩次，存儲指針比int型的空間消耗大，在圖不是很大的情況下，鄰接矩陣的空間復雜度要小。然后再確定給定的圖是否沒有奇度頂點。題目問是否存在歐拉回路即等價于問給定的圖是否為歐拉圖。所以，證明給定圖是歐拉圖就說明該圖存在歐拉回路，否則不存在歐拉回路。我們可以以鄰接矩陣的形式存儲給定的圖，對鄰接矩陣的每行分別行進行掃描，記錄每個頂點的度數(shù)，當每行掃描完后判斷該頂點的度數(shù)是否為奇數(shù)，存在奇度頂點直接結(jié)束掃描，說明存在奇度頂點，給定圖不是歐拉圖。同時選用鄰接矩陣很容易得到圖中個頂點的度數(shù)。否則繼續(xù)判斷給定的圖是否為連通圖，如果是連通圖輸出：存在歐拉回路；否則輸出：不存在歐拉回路。 printf(請輸入頂點的個數(shù)：)。 getchar()。i=e。為了排除頂點自身環(huán)對判斷的影響，當遇到邊的兩頂點相同，忽略不計，這樣不會對結(jié)果產(chǎn)生影響。j++) { if((mgedges[i][j]!=0)amp。在深度優(yōu)先搜索時。 for(i=1。//返回調(diào)用dfs函數(shù)的次數(shù)}void dfs(MGraph *mg,int i)//深度優(yōu)先搜索{ int j。（圖：1）：開始頂點數(shù)、邊數(shù)、邊信息將圖轉(zhuǎn)化為鄰接矩陣搜索圖中所有頂點的度數(shù)判斷是否存在奇度頂點 Y N對圖進行深度優(yōu)先搜索遍歷對圖進行深度優(yōu)先搜索遍歷
公司管理相關推薦
鄂ICP備17016276號-1