課程設(shè)計（論文）-基于DFS算法的圖的遍歷問題求解.docx

封皮（按學(xué)校要求手工填寫）成績評定表學(xué)生姓名郭佳晨班級學(xué)號1203060120專業(yè)通信工程課程設(shè)計題目基于dfs算法的圖的遍歷問題求解評語組長簽字：成績?nèi)掌?014 年 1月 4日課程設(shè)計任務(wù)書學(xué)院信息科學(xué)與工程學(xué)院專業(yè)通信工程學(xué)生姓名郭佳晨學(xué)號1203060120設(shè)計題目基于dfs算法的圖的遍歷問題求解實踐教學(xué)要求與任務(wù):圖作為一種非線性數(shù)據(jù)結(jié)構(gòu)，被廣泛應(yīng)用與多個技術(shù)領(lǐng)域，諸如系統(tǒng)工程、化學(xué)分析、統(tǒng)計力學(xué)、遺傳學(xué)、控制論、人工智能、編譯系統(tǒng)等領(lǐng)域，在這些技術(shù)領(lǐng)域中把圖結(jié)構(gòu)作為解決的數(shù)學(xué)手段之一。進(jìn)行類的設(shè)計與實現(xiàn)，解決圖的遍歷問題。具體要求如下：（1）采用圖的鄰接矩陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲；（2）采用遞歸程序?qū)崿F(xiàn)圖的深度優(yōu)先搜索（dfs）；（3）將上述功能作為類的成員函數(shù)實現(xiàn)，編寫主函數(shù)測試上述功能。工作計劃與進(jìn)度安排:第17周：分析題目，查閱課題相關(guān)資料，進(jìn)行類設(shè)計、算法設(shè)計；第18周：程序的設(shè)計、調(diào)試與實現(xiàn)；第19周：程序測試與分析，撰寫課程設(shè)計報告，進(jìn)行答辯驗收。指導(dǎo)教師（簽字）：年月日學(xué)院院長（簽字）年月日摘要深度優(yōu)先搜索（depth-first-search）是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當(dāng)節(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點可達(dá)的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點都被訪問為止。屬于盲目搜索。目錄1 需求分析- 3 -2 算法基本原理- 3 -3 類設(shè)計- 3 -4 詳細(xì)設(shè)計- 3 -4.1 類的成員初步設(shè)計錯誤！未定義書簽。4.2 類的成員函數(shù)設(shè)計錯誤！未定義書簽。4.3 主函數(shù)設(shè)計錯誤！未定義書簽。5 dos界面程序運行結(jié)果及分析- 3 -5.1 程序運行結(jié)果- 3 -5.2運行結(jié)果分析- 3 -6 基于mfc的圖形界面程序開發(fā)- 3 -6.1 基于mfc的圖形界面程序設(shè)計- 3 -6.2 程序測試- 3 -6.3 mfc程序編寫總結(jié)錯誤！未定義書簽。7 參考文獻(xiàn)- 3 -1 需求分析(1)圖的應(yīng)用和研究可追溯到18世紀(jì)。1736年，被稱為圖論之父的歐拉解決了哥尼斯堡（konigsberg）問題，從而奠定了圖論這門學(xué)科及其應(yīng)用的基礎(chǔ)。(2)圖作為一種非線性數(shù)據(jù)結(jié)構(gòu)，被廣泛應(yīng)用與多個技術(shù)領(lǐng)域，諸如系統(tǒng)工程、化學(xué)分析、統(tǒng)計力學(xué)、遺傳學(xué)、控制論、人工智能、編譯系統(tǒng)等領(lǐng)域，在這些技術(shù)領(lǐng)域中把圖結(jié)構(gòu)作為解決的數(shù)學(xué)手段之一。(3)程序測試數(shù)據(jù)來自姜學(xué)軍李筠主編的數(shù)據(jù)結(jié)構(gòu)（c語言描述）中，所選的無向圖是:132657482 算法基本原理(1) 鄰接矩陣是表示節(jié)點之間的相鄰接關(guān)系的矩陣。若g是有n個節(jié)點的圖，則g的鄰接矩陣是如下定義的n x n矩陣。如圖所示圖g的鄰接矩陣如下：210 1 1 11 0 1 01 1 0 11 0 1 043圖gg的鄰接矩陣(2) 圖的遍歷深度優(yōu)先搜索例如，有如下無向圖：13265748操作步驟如下：先輸出1（1為起點）；將1的鄰接頂點2和3壓入棧中；彈出棧頂元素2，由于2未被訪問過，輸出2，然后將2的鄰接頂點4 和5壓棧；彈出棧頂元素4，由于4未被訪問過，輸出4，然后將4的鄰接頂點8和2壓棧；彈出2，由于2已經(jīng)被訪問過，故彈出8，由于8未被訪問過，輸出8，再將8的鄰接頂點4、5、6、7壓棧；彈出4，由于4已經(jīng)被訪問過，故彈出5，由于5未被訪問，輸出5，然后將5的鄰接頂點2和8壓棧；彈出已經(jīng)訪問過的2和8，再彈出6，由于6未被訪問過，輸出6，再將6的鄰接頂點3和8壓棧；彈出3，由于3未被訪問過，輸出3，將3的鄰接頂點1、6、7壓棧；彈出已經(jīng)訪問過的1和6，再彈出7，由于7未被訪問過，輸出7，再將7的鄰接頂點3和8壓棧；最后彈出都已經(jīng)訪問過的3、8、8、7、5、3；此時棧為空，表示搜索結(jié)束。3 類設(shè)計本題設(shè)計的關(guān)鍵是對圖的深度優(yōu)先搜索算法的設(shè)計，由于使用鄰接矩陣來存儲圖，就要將深度優(yōu)先搜索的算法擴展到矩陣中。首先應(yīng)設(shè)計無向圖類graph，然后設(shè)計成員變量，用二維數(shù)組e來表示圖邊的權(quán)值，二維數(shù)組v來表示頂點信息，enum來表示邊的無數(shù)量，vnum來表示頂點數(shù)量，以及在遍歷中需要的訪問標(biāo)記數(shù)組visited。最后還要設(shè)計成員函數(shù)實現(xiàn)對鄰接矩陣的輸出print()，深度優(yōu)先搜索函數(shù)dfs()和遞歸調(diào)用dfs()?？紤]到圖的初始化比較復(fù)雜，需要輸入各個頂點信息，和每條邊的權(quán)值，還要設(shè)計函數(shù)initgraph()實現(xiàn)對數(shù)組的初始化。4 詳細(xì)設(shè)計由于類的設(shè)計較為簡單，將類和主函數(shù)放在同一個文件中，方便調(diào)試，首先聲明無向圖類graph，進(jìn)行類的設(shè)計，然后設(shè)計主函數(shù)，直接在主函數(shù)中實現(xiàn)類，并輸出鄰接矩陣和深度優(yōu)先搜索結(jié)果。#include#include using namespace std;constintmaxnum = 100; class graphpublic:char vmaxnum; int emaxnummaxnum;intvnum; intenum; int visitedmaxnum; graph(inta,int b); intinitgraph(); void print(); void dfs(int i); void dfs(); ; graph :graph(inta,int b) cout創(chuàng)建頂點數(shù)為a邊數(shù)b的無向圖endl; vnum=a;enum=b;for(int i=0;ivnum;i+) for(int j=0;jvnum;j+) eij = 0; int graph :initgraph()inti,j,temp,flag=0; for (i=0; ivnum; i+)cout請輸入第i+1 vi;cout請輸入各個邊的權(quán)值endl;for (i=0; ivnum; i+)for(j=i+1;jvnum;j+)cout vi vjtemp;eij = temp; eji = temp; if(temp)flag+;if(flag=enum)cout初始化無向圖鄰接矩陣完畢endl;return 0;return 1;void graph : print()cout鄰接矩陣為endl;inti,j;for (i=0; ivnum; i+)for (j=0;jvnum; j+)cout eij ;coutendl;void graph : dfs(int i) coutvi; visitedi = 1; for(int j=0;jvnum;j+) if( eij!=0 & visitedj=0) dfs(j); void graph : dfs() int i; for(i=0;ivnum;i+) visitedi = 0; for(i=0;ivnum;i+) if(visitedi=0)dfs(i);coutendl; int main() graph g(5,6); g.initgraph(); g.print();cout深度優(yōu)先搜索的結(jié)果:endl; g.dfs(); return 0; 5 dos界面程序運行結(jié)果及分析5.1 程序運行結(jié)果程序運行結(jié)果如圖2所示。圖2 程序運行結(jié)果5.2運行結(jié)果分析程序運行后首先創(chuàng)建了圖類的對象，調(diào)用構(gòu)造函數(shù)，產(chǎn)生一個頂點數(shù)為5，邊數(shù)為6的無向圖，然后初始化這個圖，輸入每個頂點的信息和每條邊的權(quán)值。在主函數(shù)中直接調(diào)用鄰接矩陣輸出函數(shù)和深度優(yōu)先搜索結(jié)果。6 基于mfc的圖形界面程序開發(fā)mfc的圖形界面程序設(shè)計可在上述類設(shè)計的基礎(chǔ)上進(jìn)行改造，mfc的圖形界面程序與dos界面程序的主要不同點是：mfc圖形界面程序與dos界面程序的輸入輸出方式不同，dos界面程序采用字符交互式實現(xiàn)數(shù)據(jù)輸入輸出，主要通過cin，cout等i/o流實現(xiàn)，而mfc的圖形程序界面采用標(biāo)準(zhǔn)windows窗口和控件實現(xiàn)輸入輸出，因此必須在mfc類的框架下加入上面所設(shè)計的圖類，并通過圖形界面的輸入輸出改造來完成。6.1 基于mfc的圖形界面程序設(shè)計（1）界面設(shè)計首先在vc中建立mfc appwizard(exe)工程，名稱為dfs，并在向?qū)У膕tep1中選擇dialog based，即建立基于對話框的應(yīng)用程序，如下圖45所示。圖4 建立mfc appwizard(exe)工程圖5 建立基于對話框的應(yīng)用程序?qū)υ捒蛸Y源中的默認(rèn)對話框利用工具箱改造成如下界面，如圖6所示。圖6 方程組求解程序界面設(shè)計圖6所示的界面中包含了1個static text控件，3個button控件，和12個edit box控件，控件的基本信息列表如下表1所示。表1 控件基本信息控件類別控件id控件caption說明static textidc_static5頂點6條邊無向圖bottonidc_button_lj鄰接矩陣idc_button_sd深度優(yōu)先遍歷idc_button_exit退出edit boxidc_edit_12 idc_edit_15鄰接矩陣的權(quán)值idc_edit_23 idc_edit_25idc_edit_34 idc_edit_35idc_edit_45（2）代碼設(shè)計為了能夠?qū)υ捒蚪缑嫔系目丶軌蚺c代碼聯(lián)系起來，需要為12個edit box控件建立member variables，按ctrl+w鍵進(jìn)入mfc classwizard界面，選擇member variables選項卡，可顯示成員變量設(shè)置界面，如圖7所示。圖7 成員變量設(shè)置界面通過該界面設(shè)置與24個edit box控件對應(yīng)的成員變量，具體如表2所示。表2 控件基本信息控件id成員變量類型成員變量名稱idc_edit_12 idc_edit_45intm_e12m_e45idc_edit_ljcstringm_ljidc_edit_sdcstringm_sd下面是編寫代碼的重要階段，可以借鑒在設(shè)計基于dos界面的控制臺應(yīng)用程序的代碼，并將其作必要的改寫，具體改寫的步驟與內(nèi)容如下。 將dfs.cpp文件重新命名為dfs.h，并將其加入mfc工程。 修改dfs.h文件具體包括：l 將顯示矩陣print()函數(shù)注釋掉，在圖形界面的程序上已經(jīng)不需要個函數(shù)承擔(dān)輸出功能了；l 將主函數(shù)注釋掉，已經(jīng)不需要主函數(shù)進(jìn)行操作了；l 將深度優(yōu)先搜索函數(shù)dfs()和dfs()的cout語句去掉，不需要也不能夠使用cout流實現(xiàn)輸出；l 將graph類的所有成員改為公共的，方便給graph類的成員變量賦值l 在graph類中聲明一個cstring型的變量dstr，用來保存函數(shù)輸出結(jié)果的字符串；l 在函數(shù)dfs內(nèi)聲明一個cstring型變量temp，用來臨時存儲函數(shù)輸出的結(jié)果，并添加以下語句temp.format(%d,i+1)；dstr+=temp； 在對話框類的實現(xiàn)文件cdfs_mfcdlg.cpp中加入#include dfs.h，以實現(xiàn)在該文件中可使用graph類。 在對話框類的實現(xiàn)文件cdfs_mfcdlg.cpp中加入graph g(5,6);,構(gòu)造一個5頂點的無向圖； 編寫鄰接矩陣按鈕的消息處理函數(shù)，實現(xiàn)圖的鄰接矩陣在界面上的顯示，具體代碼如下：voidcdfs_mfcdlg:onbuttonlj() / todo: add your control notification handler code herecstringstr1010;updatedata();g.e01=m_e12;g.e10=m_e12;g.e02=m_e13;g.e20=m_e13;g.e03=m_e14;g.e30=m_e14;g.e04=m_e15;g.e40=m_e15;g.e12=m_e23;g.e21=m_e23;g.e13=m_e24;g.e31=m_e24;g.e14=m_e25;g.e41=m_e25;g.e23=m_e34;g.e32=m_e34;g.e24=m_e35;g.e42=m_e35;g.e34=m_e45;g.e43=m_e45;m_lj=;updatedata(0);for (int i=0;i5;i+)for (int j=0;j5;j+)strij.format(%i,g.eij);m_lj+=strij;m_lj+=rn;updatedata(0); 編寫深度優(yōu)先遍歷按鈕的消息處理函數(shù)，實現(xiàn)對圖的深度遍歷，并顯示到界面上，具體代碼如下：voidcdfs_mfcdlg:onbuttonsd() / todo: add your control notification handler code herecstringstr1010;updatedata();g.e01=m_e12;g.e10=m_e12;g.e02=m_e13;g.e20=m_e13;g.e03=m_e14;g.e30=m_e14;g.e04=m_e15;g.e40=m_e15;g.e12=m_e23;g.e21=m_e23;g.e13=m_e24;g.e31=m_e24;g.e14=m_e25;g.e41=m_e25;g.e23=m_e34;g.e32=m_e34;g.e24=m_e35;g.e42=m_e35;g.e34=m_e45;g.e43=m_e45;g.dstr=;g.dfs();m_sd=;updatedata(0);m_sd=g.dstr;updatedata(0);退出按鈕代碼如下：voidcguasslineguidlg:onbuttonexit() / todo: add your control notification handler code hereonok();6.2程序測試運行程序后，首先出現(xiàn)的界面如圖8所示。圖8程序初始運行界面在編輯框輸入鄰接矩陣的權(quán)值后，單擊鄰接矩陣按鈕，可將這個5頂點的無向圖鄰接矩陣在界面上顯示出來，如圖9所示。圖9讀入數(shù)據(jù)后的界面單擊深度優(yōu)先遍歷按鈕，實現(xiàn)對圖的深度優(yōu)先搜索并顯示出搜索結(jié)果，如圖10所示。圖10求解方程組后的界面單擊退出按鈕后，程序能夠正常實現(xiàn)退出。7結(jié)論mfc為windows應(yīng)用程序開發(fā)者提供了一種快速開發(fā)的工具，尤其是mf