數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告(已修改)
2025-04-26 04:41 本頁面
【正文】 合肥學院計算機科學與技術(shù)系課程設(shè)計報告2012 ～2013 學年第 2 學期課程 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程設(shè)計課程設(shè)計名稱歐拉回路學生姓名陶飛學號1104012039專業(yè)班級計算機科學與技術(shù)11級3班指導教師李紅，何立新，華珊珊，陳艷平2013 年 3月題目：歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路?，F(xiàn)給定一個圖，問是否存在歐拉回路？一．問題分析和任務(wù)定義：題目要求判斷一個給定的圖中是否存在歐拉回路。由歐拉圖的定義，當一個圖存在歐拉回路時，該圖稱為歐拉圖。題目問是否存在歐拉回路即等價于問給定的圖是否為歐拉圖。所以，證明給定圖是歐拉圖就說明該圖存在歐拉回路，否則不存在歐拉回路。根據(jù)高等教育出版社出版屈婉玲、耿素云、張立昂主編的《離散數(shù)學》：無向圖G是歐拉圖當且僅當G是連通圖且沒有奇度頂點。要證明一個給定的圖是否為歐拉圖，證明給定的圖是連通圖且沒有奇度頂點即可。所以，解決題目中的問題就轉(zhuǎn)化為證明給定圖是否是連通圖且沒有奇度頂點。首先要確定一給定的圖是否為連通圖。這里我們可以通過圖的深度優(yōu)先搜索遍歷確定。從任意頂點出發(fā)，如果能深度優(yōu)先遍歷到所有的頂點就說明圖中所有的頂點都是連圖的即為連通圖。然后再確定給定的圖是否沒有奇度頂點。我們可以以鄰接矩陣的形式存儲給定的圖，對鄰接矩陣的每行分別行進行掃描，記錄每個頂點的度數(shù)，當每行掃描完后判斷該頂點的度數(shù)是否為奇數(shù)，存在奇度頂點直接結(jié)束掃描，說明存在奇度頂點，給定圖不是歐拉圖。即不存在歐拉回路。否則繼續(xù)掃描，當掃描完所有的行沒有發(fā)現(xiàn)奇度頂點，即說明給定圖沒有奇度頂點。當上述兩個問題都確定以后根據(jù)定理，當且僅當給定圖為連通圖且沒有奇度頂點時給定的圖為歐拉圖。由此可確定，給定的圖是否存在歐拉回路。二．數(shù)據(jù)結(jié)構(gòu)的選擇與概要設(shè)計：1． 數(shù)據(jù)結(jié)構(gòu)的選擇：圖在我們所學的數(shù)據(jù)結(jié)構(gòu)與算法課程中有四種存儲方式：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。本問題比較簡單，選用鄰接矩陣或鄰接矩陣就足夠了。在本課程設(shè)計中需要判斷是否有奇度頂點和是否為連通圖，用用鄰接表和鄰接矩陣在時間繁雜度沒有什么大的差別，在空間復雜度上，因為本題是無向圖，如果如果用鄰接表，儲存一條邊要儲存兩次，存儲指針比int型的空間消耗大，在圖不是很大的情況下，鄰接矩陣的空間復雜度要小。同時選用鄰接矩陣很容易得到圖中個頂點的度數(shù)。因為頂點只要求編號這一信息，所以就沒有用結(jié)構(gòu)體存儲頂點信息，圖用鄰接矩陣要用結(jié)構(gòu)體存儲。結(jié)構(gòu)體定義如下：typedef struct{ int n。//頂點個數(shù) int e。//邊的條數(shù) int vexs[MAX_VERTEX_NUM]。//一維數(shù)組儲存頂點 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。//二維數(shù)組儲存邊}MGraph。//圖首先將圖轉(zhuǎn)換為鄰接矩陣存儲起來，然后鄰接矩陣的每一行進行搜索得圖中到每個頂點的度數(shù)，如果有奇度頂點，輸出：不存在歐拉回路，即可結(jié)束程序。否則繼續(xù)判斷給定的圖是否為連通圖，如果是連通圖輸出：存在歐拉回路；否則輸出：不存在歐拉回路。結(jié)束程序。三．詳細設(shè)計和編碼：：先輸入圖中頂點個個數(shù)和邊的條數(shù)，對所有可能存在的邊初始化為0，再依
公司管理相關(guān)推薦
鄂ICP備17016276號-1