1、 C+課程設計課程設計(論文論文)成成 績績 評評 定定 表表學生姓名xxx班級學號xxx專 業通信工程課程設計題目基于 DFS 算法的圖的遍歷問題求解評語組長簽字：成績日期 20 年 月 日課程設計任務書課程設計任務書學 院信息科學與工程專 業通信工程學生姓名xxx班級學號xxx課程設計題目基于 DFS 算法的圖的遍歷問題求解實踐教學要求與任務實踐教學要求與任務圖作為一種非線性數據結構，被廣泛應用與多個技術領域，諸如系統工程、化學分析、統計力學、遺傳學、控制論、人工智能、編譯系統等領域，在這些技術領域中把圖結構作為解決的數學手段之一。進行類的設計與實現，解決圖的遍歷問題。具體要求如下：（1）

2、采用圖的鄰接矩陣或鄰接表實現最短路徑問題中圖的存儲；（2）采用遞歸程序實現圖的深度優先搜索（DFS） ；（3）將上述功能作為類的成員函數實現，編寫主函數測試上述功能。工作計劃與進度安排工作計劃與進度安排第 17 周：分析題目，查閱課題相關資料，進行類設計、算法設計；第 18 周：程序的設計、調試與實現；第 19 周：程序測試與分析，撰寫課程設計報告，進行答辯驗收。指導教師： 201 年 月 日專業負責人： 201 年 月 日學院教學副院長： 201 年 月 日摘 要本文采用圖的鄰接矩陣實現了最短路徑問題中圖的存儲；采用遞歸程序實現了圖的深度優先搜索（DFS） ，用類的成員函數實現了其各個功能。

3、類是所有 C+語言的一大特征，是實現本程序設計的基礎。圖是一種比較復雜的非線性數據結構，深度優先搜索（DFS）是圖的遍歷的方法之一，它是指按照深度方向實現圖的每個結點的搜索，類似于樹的先根遍歷訪問了圖的每一個結點，而采用鄰接矩陣可以實現圖的最短路徑存儲，提高程序的優越性。本 C+程序實現了圖的最短路徑存儲及遍歷，采用Visual C+ 6.0 的控制臺工程和 MFC 工程分別實現了鄰接矩陣在桌面上的的顯示以及實現對圖的深度遍歷程序，通過對兩種程序的測試結果表明：基于算法的圖的遍歷算法原理正確，兩種程序均能正確求解給定的圖的遍歷問題。關鍵詞：鄰接矩陣，類的成員函數，遞歸調用，深度優先搜索，控制臺

4、工程，圖形界面。目目 錄錄1、需求分析、需求分析.12、算法基本原理、算法基本原理.13、類設計、類設計.34、基于控制臺的應用程序、基于控制臺的應用程序.34.1 類的接口設計.34.2 類的成員函數設計.44.3 主函數設計.65、基于控制臺、基于控制臺的的應用程序設計應用程序設計.65.1 程序運行結果.65.2 運行結果分析.76、基于、基于 MFC 的圖形界面程序開發的圖形界面程序開發.76.1 基于 MFC 的圖形界面程序設計.86.2 程序測試.13結論結論.14參考文獻參考文獻.15第 0 頁 共 21 頁1 1、需求分析、需求分析（1）圖作為一種非線性數據結構，被廣泛應用與多

5、個技術領域本設計依靠類的成員函數完成以下功能：采用圖的鄰接矩陣實現最短路徑問題中圖的存儲；采用遞歸程序實現圖的深度優先搜索（DFS） 。采用 Visual C+ 6.0 的控制臺工程和 MFC 工程分別實現鄰接矩陣在桌面上的的顯示以及實現對圖的深度遍歷程序。（2）程序測試數據來自姜學軍、李筠主編的數據結構（C 語言描述） 中，所選的無向圖是:2 2、算法基本原理、算法基本原理(1)鄰接矩陣是表示節點之間的相鄰接關系的矩陣。若 G 是有 n 個節點的圖，則 G 的鄰接矩陣是如下定義的 n X n 矩陣。如圖所示圖 G 的鄰接矩陣如下： 圖 G G 的鄰接矩陣1328765414320 1 1 1

6、1 0 1 01 1 0 11 0 1 0第 1 頁 共 21 頁(2)圖的遍歷深度優先搜索例如，有如下無向圖：操作步驟如下： 先輸出 1（1 為起點） ； 將 1 的鄰接頂點 2 和 3 壓入棧中； 彈出棧頂元素 2，由于 2 未被訪問過，輸出 2，然后將 2 的鄰接頂點 4 和5 壓棧； 彈出棧頂元素 4，由于 4 未被訪問過，輸出 4，然后將 4 的鄰接頂點 8 和 2壓棧； 彈出 2，由于 2 已經被訪問過，故彈出 8，由于 8 未被訪問過，輸出 8，再將 8 的鄰接頂點 4、5、6、7 壓棧； 彈出 4，由于 4 已經被訪問過，故彈出 5，由于 5 未被訪問，輸出 5，然后將 5 的

7、鄰接頂點 2 和 8 壓棧； 彈出已經訪問過的 2 和 8，再彈出 6，由于 6 未被訪問過，輸出 6，再將 6的鄰接頂點 3 和 8 壓棧； 彈出 3，由于 3 未被訪問過，輸出 3，將 3 的鄰接頂點 1、6、7 壓棧； 彈出已經訪問過的 1 和 6，再彈出 7，由于 7 未被訪問過，輸出 7，再將 7的鄰接頂點 3 和 8 壓棧； 最后彈出都已經訪問過的 3、8、8、7、5、3；此時棧為空，表示搜索結束。13287654第 2 頁 共 21 頁3 3、類設計、類設計本題設計的關鍵，是對圖的深度優先搜索算法的設計，由于使用鄰接矩陣來存儲圖，就要將深度優先搜索的算法擴展到矩陣中。首先，應設計

8、無向圖類 graph，然后設計成員變量，用二維數組 e 來表示圖邊的權值，二維數組 v 來表示頂點信息，eNum 用來表示邊的無數量，vNum 用來表示頂點數量，以及在遍歷中需要的訪問標記數組 visited。最后還要設計成員函數，實現對鄰接矩陣的輸出 print()，深度優先搜索函數 DFS()和遞歸調用 dfs()。考慮到圖的初始化比較復雜，需要輸入各個頂點信息，和每條邊的權值，還要設計函數 InitGraph()實現對數組的初始化。4 4、基于控制臺的應用程序基于控制臺的應用程序由于類的設計較為簡單，將類和主函數放在同一個文件中，方便調試，首先聲明無向圖類 graph，進行類的設計，然后

9、設計主函數，直接在主函數中實現類，并輸出鄰接矩陣和深度優先搜索結果。4.1 類的接口設計/*聲明區*/ #include /*頭文件包含 malloc 函數，用來申請內存空間*/ #include#include#include const int maxnum=100; /*設置鄰接矩陣的最大階數*/ /*圖類的鄰接矩陣表示*/ class Graphpublic: char vmaxnum; /*圖的頂點信息*/ int emaxnummaxnum; /*圖的邊權值 */ 第 3 頁 共 21 頁 int vNum; /*頂點個數 */ int eNum; /*邊的個數 */ int vi

10、sitedmaxnum; /*標記這個頂點是否被訪問過,0 表示沒有,1 表示已經被訪問過*/public: void graph(int a,int b); /*構造函數 */ int InitGraph(); /*圖類的初始化函數*/ void print(); /*輸出鄰接矩陣 */ void dfs(int i); /*深度優先搜索 */ void DFS();4.2 類的成員函數設計/*構造函數*/void Graph:graph(int a,int b) cout創建頂點數為a邊數b的無向圖endl; vNum=a; eNum=b; /*為了防止原先存在 e中的數據對今后的搜索造成

11、影響,所以對其進行初始化*/ for(int i=0;i vNum;i+) for(int j=0;j vNum;j+)eij = 0; int Graph:InitGraph()int i,j,temp,flag=0; for (i=0;ivNum;i+)cout請輸入第i+1vi;/*輸入各個邊的具體情況*/ cout請輸入各個邊的權值endl;for (i=0;ivNum;i+)for(j=i+1;jvNum;j+)第 4 頁 共 21 頁coutvivjtemp;eij=temp; eji=temp; if(temp)flag+;if(flag=eNum)cout初始化無向圖鄰接矩陣完

12、畢endl;return 0;return 1;/*輸出鄰接矩陣*/ void Graph:print()cout鄰接矩陣為endl; int i,j; for (i=0;ivNum;i+)for (j=0;jvNum;j+)couteij ;coutendl; /*深度優先搜索*/void Graph:dfs(int i) coutvi; /*i 已經被訪問*/ visitedi=1; /*標記 i 邊已經被訪問*/ for(int j=0;jvNum;j+) /*對與 i 點與全部節點進行掃描*/ if(eij!=0)&(visitedj=0) /*假如 j 點與 i 點相連,并且

13、 j 點還沒有被訪問過*/ dfs(j); /*遞歸方法,對 j 點進行深度優先搜索*/ void Graph:DFS() int i; /*首先把所有點都設置成沒有訪問過 */ for(i=0;ivNum;i+)第 5 頁 共 21 頁 visitedi=0; /*深度優先搜索*/ for(i=0;ivNum;i+) if(visitedi=0) /*假如 i 點沒有被訪問過*/ dfs(i); /*對以鄰接矩陣表示的圖，以序號為 i 的頂點為出發點進行 DFS*/ coutendl; 4.3 主函數設計int main() /*以下兩個語句用來建立用鄰接矩陣表示的圖*/ Graph gra

14、ph(4,3); graph.InitGraph(); /*創建圖*/ graph.print(); cout深度優先搜索的結果:endl; graph.DFS(); return 0; 5 5、基于控制臺的應用程序設計、基于控制臺的應用程序設計5.15.1 程序運行結果程序運行結果程序運行結果如圖 1 所示。第 6 頁 共 21 頁圖 1 程序運行結果5.25.2 運行結果分析運行結果分析 程序運行后首先創建了圖類的對象，調用構造函數，產生一個頂點數為 5，邊數為 6 的無向圖，然后初始化這個圖，從鍵盤輸入每個頂點的信息（a b c d e）和每條邊的權值。在主函數中直接調用鄰接矩陣輸出函數

15、和深度優先搜索結果。6 6、基于、基于 MFCMFC 的圖形界面程序開發的圖形界面程序開發MFC 的圖形界面程序設計可在上述類設計的基礎上進行改造，MFC 的圖形界面程序與 DOS 界面程序的主要不同點是：MFC 圖形界面程序與 DOS 界面程序的輸入輸出方式不同，DOS 界面程序采用字符交互式實現數據輸入輸出，主要通過 cin，cout 等 I/O 流實現，而 MFC 的圖形程序界面采用標準 Windows 窗口和控件實現輸入輸出，因此必須在MFC 類的框架下加入上面所設計的圖類，并通過圖形界面的輸入輸出改造來完成。第 7 頁 共 21 頁6.16.1 基于基于 MFCMFC 的圖形界面程序

16、設計的圖形界面程序設計（1 1）界面設計）界面設計首先在 VC 中建立 MFC AppWizard(exe)工程，名稱為 DFS，并在向導的 Step1 中選擇 Dialog based，即建立基于對話框的應用程序，如下圖 45 所示。圖 2 建立 MFC AppWizard(exe)工程圖 3 建立基本對話框的應用程序第 8 頁 共 21 頁將對話框資源中的默認對話框利用工具箱改造成如下界面，如圖 4 所示。圖 6 方程組求解程序界面設計圖 4 方程組求解程序界面設計圖 4 所示的界面中包含了 1 個 Static Text 控件，3 個 Button 控件，和 12 個 Edit Box

17、控件，控件的基本信息列表如下表 1 所示。表 1 控件基本信息控件類別控件 ID控件 Caption說明Static TextIDC_STATIC5 頂點 6 條邊無向圖IDC_BUTTON_LJ鄰接矩陣IDC_BUTTON_SD深度優先遍歷BottonIDC_BUTTON_Exit退出IDC_EDIT_12 IDC_EDIT_15IDC_EDIT_23 IDC_EDIT_25IDC_EDIT_34 IDC_EDIT_35Edit BoxIDC_EDIT_45鄰接矩陣的權值（2）代碼設計）代碼設計為了能夠將對話框界面上的控件能夠與代碼聯系起來，需要為 12 個 Edit Box 控第 9 頁

18、共 21 頁件建立 Member Variables，按 Ctrl+w 鍵進入 MFC ClassWizard 界面，選擇 Member Variables 選項卡，可顯示成員變量設置界面，如圖 5 所示。通過該界面設置與 24 個 Edit Box 控件對應的成員變量，具體如表 2 所示。表 2 控件基本信息控件 ID成員變量類型成員變量名稱IDC_EDIT_12 IDC_EDIT_45intm_e12m_e45IDC_EDIT_LJCStringm_LJIDC_EDIT_SDCStringm_SD下面是編寫代碼的重要階段，可以借鑒在設計基于 DOS 界面的控制臺應用程序的代碼，并將其作必要

19、的改寫，具體改寫的步驟與內容如下。 將 DFS.cpp 文件重新命名為 DFS.h，并將其加入 MFC 工程。 修改 DFS.h 文件具體包括：將顯示矩陣 print()函數注釋掉，在圖形界面的程序上已經不需要個函數承擔輸出功能了；圖 5 成員變量設置界面第 10 頁 共 21 頁將主函數注釋掉，已經不需要主函數進行操作了； 將深度優先搜索函數 DFS()和 dfs()的 cout 語句去掉，不需要也不能夠使用 cout流實現輸出；將 graph 類的所有成員改為公共的，方便給 graph 類的成員變量賦值在 graph 類中聲明一個 CString 型的變量 Dstr，用來保存函數輸出結果的

20、字符串；在函數 dfs 內聲明一個 CString 型變量 temp，用來臨時存儲函數輸出的結果，并添加以下語句 temp.Format(%d,i+1)；Dstr+=temp； 在對話框類的實現文件 CDFS_MFCDlg.cpp 中加入#include DFS.h，以實現在該文件中可使用 graph 類。 在對話框類的實現文件 CDFS_MFCDlg.cpp 中加入 graph g(5,6);,構造一個 5 頂點的無向圖； 編寫鄰接矩陣按鈕的消息處理函數，實現圖的鄰接矩陣在界面上的顯示，具體代碼如下：void CDFS_MFCDlg:OnButtonLj() / TODO: Add your

21、 control notification handler code hereCString str1010;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;第 11 頁 共 21 頁g.

22、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); 編寫深度優先遍歷按鈕的消息處理函數，實現對圖的深度遍歷，并顯示到界面上，具體代碼如下：void CDFS_MFCDlg:OnButtonSd() / TODO: Add your control notification handler code hereCString str1010;UpdateData();g.

23、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;第 12 頁 共 21 頁 g.Dstr=;g.DFS();m_SD=; UpdateData(0);m_SD=g.Dstr;UpdateData(0);退出按鈕代碼如下：void CGuassLineGUIDlg:OnBUTTONExit() / TODO: Add your control notification handler code hereOnOK();6.26.2 基于基于 MFCMFC 的應用程序測試的應用程序測試運行程序后，首先出現的界面如圖 6 所示。圖 6 程序初始運行界面在編輯框輸入鄰接矩陣的權值后，單擊鄰接矩陣按鈕，可將這個 5 頂點的無向圖鄰第 13 頁 共 21 頁接矩陣在界面上顯示出來，如圖 7 所示。圖 7 程序運行后的界面單擊退出