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