基于BFS算法的圖的遍歷設(shè)計與實現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上0摘 要本文采用圖的鄰接矩陣實現(xiàn)了最短路徑問題中圖的存儲；采用隊列實現(xiàn)了圖的廣度優(yōu)先搜索（BFS），用類的成員函數(shù)實現(xiàn)了其各個功能。本C+程序?qū)崿F(xiàn)了圖的最短路徑存儲及BFS遍歷，采用Visual C+ 6.0的控制臺工程和MFC工程分別實現(xiàn)了鄰接矩陣在桌面上的的顯示以及實現(xiàn)對圖的廣度遍歷程序，通過對兩種程序的測試結(jié)果表明：基于BFS算法的圖的遍歷算法原理正確，兩種程序均能正確求解給定的圖的遍歷問題。關(guān)鍵詞:鄰接矩陣；隊列；廣度優(yōu)先搜索；控制臺工程；MFC圖形界面目 錄專心-專注-專業(yè)1 需求分析(1)圖的應(yīng)用和研究可追溯到18世紀。1736年，被稱

2、為圖論之父的歐拉解決了哥尼斯堡（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語言描述）中，所選的無向圖是:13265748圖 1 2 算法基本原理2.1 鄰接矩陣鄰接矩陣是表示節(jié)點之間的相鄰接關(guān)系的矩陣。若G是有n個節(jié)點的圖，則G的鄰接矩陣是如下定義的n X n矩陣。如圖所示圖G的鄰接矩陣如下：210 1 1 11 0 1 01 1 0 1

3、1 0 1 043 圖G G的鄰接矩陣2.2 圖的遍歷廣度優(yōu)先搜索(BFS）例如，有如下無向圖：13265748操作步驟如下：先輸出1（1為起點）,將1入隊；1出隊，由于1的鄰接頂點2和3未被訪問過，輸出2和3并將2和3入隊；2出隊,2的鄰接頂點1;3出隊，由于3的鄰接頂點1被訪問過，而鄰接頂點6和7未被訪問過，輸出6和7并將6和7入隊；4出隊，由于4的鄰接頂點2被訪問過，而鄰接頂點8未被訪問過，輸出8并將8入隊；最后5，6，7，8出隊，由于它們的鄰接頂點都被訪問過；此時隊空，表示搜索已結(jié)束。3 類設(shè)計3.1 類的概述本題設(shè)計的關(guān)鍵是對圖的廣度優(yōu)先搜索算法的設(shè)計，由于使用鄰接矩陣來存儲圖，就要

4、將廣度優(yōu)先搜索的算法擴展到矩陣中。首先應(yīng)設(shè)計無向圖類Graph然后設(shè)計成員變量，用二維數(shù)組edge來表示圖邊的權(quán)值，一維數(shù)組vertex來表示頂點信息，eNum來表示邊的數(shù)量，vNum來表示頂點數(shù)量，以及在遍歷中需要的訪問標記數(shù)組visited。最后還要設(shè)計成員函數(shù)實現(xiàn)對鄰接矩陣的輸出print()，廣度優(yōu)先搜索函數(shù)BFS()?？紤]到圖的初始化比較復(fù)雜，需要Graph(int a,int b)輸入各個頂點信息，int InitGraph()輸入每條邊的權(quán)值。由于調(diào)用BFS()需要用到隊列，還需要設(shè)計結(jié)點類QueueNode和隊列類LinkQueue；用data表示結(jié)點數(shù)據(jù)，*next表示結(jié)點指

5、針域，使用構(gòu)造函數(shù)QueueNode()對結(jié)點進行初始化;用*front和*rear表示隊列的前驅(qū)和后繼，使用void Init_Queue()對隊列進行初審，判斷隊列是否為空: void Init_Queue(),入隊類操作: int En_Queue(DataType e),出隊列操作: void De_Queue(DataType &e)。由于程序比較復(fù)雜，Graph類的接口實現(xiàn)放在Graph.h中, QueueNode類和LinkQueue類的接口放在Queue.h中，類的實現(xiàn)和主函數(shù)放在main.cpp中。3.2類的接口設(shè)計*/Graph.hGraph類的接口設(shè)計using

6、namespace std; const int maxnum=100; /設(shè)置鄰接矩陣的最大階數(shù) class Graph private: char vertexmaxnum; /圖的頂點信息 int edgemaxnummaxnum; /圖的邊信息 int vNum; /頂點個數(shù) int eNum; /邊的個數(shù) bool visitedmaxnum; /標記這個頂點是否被訪問過,0表示沒有,1表示已經(jīng)被訪問過 public: Graph(int a,int b); /構(gòu)造函數(shù) int InitGraph(); /圖類的初始化函數(shù) void print();/輸出鄰接矩陣 void BFS(

7、); /廣度優(yōu)先遍歷鄰接矩陣 ;*/Queue.hQueueNode類和LinkQueue類的接口設(shè)計：typedef int DataType;class QueueNodepublic:DataType data;QueueNode *next;QueueNode()next=NULL;class LinkQueuepublic:QueueNode *front;QueueNode *rear;LinkQueue();/構(gòu)造函數(shù)void Init_Queue()/初始化front=NULL;rear=NULL;LinkQueue()/析構(gòu)函數(shù)QueueNode *p,*q;p=front;

8、while(p)q=p;p=p->next;delete q;front=NULL;rear=NULL;int Empty_Queue();/判斷隊列是否為空int En_Queue(DataType e);/入隊列操作void De_Queue(DataType &e);/出隊列操作;3.3 類的實現(xiàn)/main.cppint LinkQueue:Empty_Queue() return(front=NULL&&rear=NULL);int LinkQueue:En_Queue(DataType e)QueueNode *p=new QueueNode;if(p)

9、 /判斷是否申請成功p->data=e;if(rear)rear->next=p;else front=rear=p; return 1;elsereturn 0;void LinkQueue:De_Queue(DataType &e)QueueNode *p;if(!Empty_Queue()p=front;e=p->data;front=front->next;if(!front)rear=NULL;delete p;Graph:Graph(int a,int b) cout<<"創(chuàng)建頂點數(shù)為"<<a<<

10、;"邊數(shù)"<<b<<"的無向圖"<<endl; vNum=a; eNum=b; /為了防止原先存在e中的數(shù)據(jù)對今后的搜索造成影響,所以對其進行初始化 for(int i=0;i< vNum;i+) for(int j=0;j< vNum;j+) edgeij = 0; int Graph:InitGraph() int i,j,temp,flag=0; for (i=0;i<vNum;i+) cout<<"請輸入第"<<i+1<<"個頂

11、點信息:" cin>>vertexi; /輸入各個邊的具體情況 cout<<"請輸入各個邊的權(quán)值"<<endl; for (i=0;i<vNum;i+) for(j=i+1;j<vNum;j+) cout<<vertexi<<"->"<<vertexj<<"：" cin>>temp; edgeij=temp; edgeji=temp; if(temp)flag+; if(flag=eNum) cout<&l

12、t;"初始化無向圖鄰接矩陣完畢"<<endl; return 0; return 1; /輸出鄰接矩陣 void Graph:print() cout<<"鄰接矩陣為"<<endl; int i,j; for (i=0;i<vNum;i+) for (j=0;j<vNum;j+) cout<<edgeij<<" " cout<<endl; void Graph:BFS()cout<<"廣度優(yōu)先搜索（BFS）"<&l

13、t;endl;int i,j;LinkQueue Q;/生成輔助隊列對象Qfor(i=0;i<vNum;+i)visitedi=false;/訪問標志數(shù)組初始化Q.Init_Queue();/初始化隊列Qfor(i=0;i<vNum;+i)if(!visitedi)/對未訪問的頂點進行收縮visitedi=true;cout<<vertexi<<" "Q.En_Queue(i);while(!Q.Empty_Queue()/隊列非空int m;Q.De_Queue(m);for(j=0;j<vNum;j+)if(edgemj=1)&

14、amp;&(!visitedj)visitedj=true;cout<<vertexj<<" "Q.En_Queue(j);4 基于控制臺的應(yīng)用程序4.1主函數(shù)設(shè)計int main() int x,y; cout<<"請輸入頂點數(shù)x="cin>>x; y=x*(x-1)/2; Graph G(x,y); G.InitGraph(); G.print(); G.BFS(); cout<<endl; return 0; 4.2運行結(jié)果分析圖1程序運行結(jié)果程序運行后首先創(chuàng)建了圖類的對象，調(diào)用構(gòu)

15、造函數(shù)，產(chǎn)生一個頂點數(shù)為6，邊數(shù)為15的無向圖，然后初始化這個圖，從鍵盤輸入每個頂點的信息（a b c d e f）和每條邊的權(quán)值。在主函數(shù)中直接調(diào)用鄰接矩陣輸出函數(shù)和廣度優(yōu)先搜索結(jié)果。5 基于MFC的應(yīng)用程序MFC的圖形界面程序設(shè)計可在上述類設(shè)計的基礎(chǔ)上進行改造，MFC的圖形界面程序與DOS界面程序的主要不同點是：MFC圖形界面程序與DOS界面程序的輸入輸出方式不同，DOS界面程序采用字符交互式實現(xiàn)數(shù)據(jù)輸入輸出，主要通過cin，cout等I/O流實現(xiàn)，而MFC的圖形程序界面采用標準Windows窗口和控件實現(xiàn)輸入輸出，因此必須在MFC類的框架下加入上面

16、所設(shè)計的矩陣和方程組類，并通過圖形界面的輸入輸出改造來完成。5.1 圖形界面設(shè)計首先在VC中建立MFC AppWizard（exe）工程，名稱為課程設(shè)計MFC，并在向?qū)У腟tep1中選擇Dialog based，即建立基于對話框的應(yīng)用程序，如圖23所示。其余Steps均為默認選項。圖2 建立MFC AppWizard（exe）工程圖3 建立基于對話框的應(yīng)用程序?qū)υ捒蛸Y源中的默認對話框利用工具箱改造成如圖4所示界面圖4圖4所示的界面中包含了11個Static Text控件，4個Button控件，和12個Edit Box控件，控件的基本信息列表如下表1所示。表1 控件基本信息控件類別控件ID控件

17、Caption說明Static TextIDC_STATIC5頂點無向圖各邊的權(quán)值a->ba->ca->da->eb->cb->db->ec->dc->ed->eBottonIDC_BUTTON_LJ鄰接矩陣IDC_BUTTON_BFS廣度優(yōu)先遍歷IDC_BUTTON_CLEAN清空IDCANCEL退出Edit BoxIDC_EDIT_12鄰接矩陣的權(quán)值IDC_EDIT_13IDC_EDIT_14IDC_EDIT_15 IDC_EDIT_23IDC_EDIT_24 IDC_EDIT_25IDC_EDIT_34IDC_EDIT_35ID

18、C_EDIT_45IDC_EDIT_MATRIX顯示鄰接矩陣IDC_EDIT_COUT顯示遍歷結(jié)果5.2 程序代碼設(shè)計為了能夠?qū)υ捒蚪缑嫔系目丶軌蚺c代碼聯(lián)系起來，需要為12個Edit Box控件建立Member Variables，按Ctrl+w鍵進入MFC ClassWizard界面，選擇Member Variables選項卡，可顯示成員變量設(shè)置界面，如圖5所示。圖5 成員變量設(shè)置界面下面是編寫代碼的重要階段，可以借鑒在設(shè)計基于DOS界面的控制臺應(yīng)用程序的代碼，并將其作必要的改寫，具體改寫的步驟與內(nèi)容如下。(1).將基于控制臺應(yīng)用程序的頭文件Queue.h、Graph.h加入到MFC工程

19、的頭文件中，同時將控制臺應(yīng)用程序的源文件main.cpp改名為premain.h加入到MFC的頭文件中，同時需要修改部分：a.刪除main.cpp(premain.h)的主函數(shù)int main()。b.刪除main.cpp(premain.h)的刪除print()函數(shù)。c.把Graph.h中的Graph類的所有成員該為public。d.在Graph.h中的Graph類聲明一個Cstring型變量Dstr。e.在BFS()函數(shù)中CString 型變量temp。f.將BFS()函數(shù)中的cout語句刪除，同時將BFS()函數(shù)的部分代碼修改：在刪除cout語句的地方加上 temp.Format(&qu

20、ot;%d ",i+1);Dstr+=temp; 兩條語句。(2).在對話框類的實現(xiàn)文件課程設(shè)計MFCDlg.cpp加入#include "premain.h"(在premain.h中已經(jīng)包含了”Queue.h”、”Graph.h”)，以實現(xiàn)在該文件中可使用Graph類。(3). 在對話框類的實現(xiàn)文件課程設(shè)計MFCDlg.cpp中加入Graph g(5,6);,構(gòu)造一個5頂點的無向圖。(4).如圖所示：示意圖雙擊鄰接矩陣按鈕、廣度優(yōu)先搜索按鈕、清空按鈕，分別為其建立響應(yīng)函數(shù)：鄰接矩陣的響應(yīng)函數(shù)OnButtonLj()；廣度優(yōu)先搜索的響應(yīng)函數(shù)OnButtonBfs(

21、)；清空的響應(yīng)函數(shù)OnButtonClean()(5). 鄰接矩陣的響應(yīng)函數(shù)代碼（OnButtonLj()）：void CMFCDlg:OnButtonLj() CString str1010;UpdateData(TRUE); g.edge01=m_e12; g.edge10=m_e12; g.edge02=m_e13; g.edge20=m_e13; g.edge03=m_e14; g.edge30=m_e14; g.edge04=m_e15; g.edge40=m_e15; g.edge12=m_e23; g.edge21=m_e23; g.edge13=m_e24; g.edge31=

22、m_e24; g.edge14=m_e25; g.edge41=m_e25; g.edge23=m_e34; g.edge32=m_e34; g.edge24=m_e35; g.edge42=m_e35; g.edge34=m_e45; g.edge43=m_e45;m_str_matrix="" UpdateData(0); for(int i=0;i<5;i+) for(int j=0;j<5;j+) strij.Format("%i,",g.edgeij); m_str_matrix+=strij; m_str_matrix+=&quo

23、t;rn" UpdateData(FALSE); UpdateData(FALSE); (6). 廣度優(yōu)先搜索的響應(yīng)函數(shù)代碼（OnButtonBfs()）：void CMFCDlg:OnButtonBfs() / TODO: Add your control notification handler code hereint x;CString str1010;UpdateData(TRUE); g.edge01=m_e12; g.edge10=m_e12; g.edge02=m_e13; g.edge20=m_e13; g.edge03=m_e14; g.edge30=m_e14;

24、 g.edge04=m_e15; g.edge40=m_e15; g.edge12=m_e23; g.edge21=m_e23; g.edge13=m_e24; g.edge31=m_e24; g.edge14=m_e25; g.edge41=m_e25; g.edge23=m_e34; g.edge32=m_e34; g.edge24=m_e35; g.edge42=m_e35; g.edge34=m_e45; g.edge43=m_e45;g.Dstr=""g.BFS();m_str_cout=""UpdateData(FALSE);for(x=0;

25、x<5;x+)m_str_cout+=g.Dstr.GetAt(2*x)+'0'm_str_cout.MakeUpper();UpdateData(FALSE);(7). 清空的響應(yīng)函數(shù)代碼（OnButtonClean()）void CMFCDlg:OnButtonClean() / TODO: Add your control notification handler code hereUpdateData(TRUE);m_e12=0;m_e13=0;m_e14=0;m_e15=0;m_e23=0;m_e24=0;m_e25=0;m_e34=0;m_e35=0;m_e4

26、5=0;m_str_matrix=""m_str_cout=""UpdateData(FALSE);5.3 運行結(jié)果及分析運行程序后，首先出現(xiàn)的界面如圖6所示。圖6 程序初始運行界面分別輸入a->b、a->c、a->c、a->d、a->e、b->c、b->d、b->e、c->d、c->e、d->e，單擊鄰接矩陣按鈕后，可將此無向圖的鄰接矩陣表示出現(xiàn)對話框中，如圖7所示。圖7 點擊鄰接矩陣按鈕后的界面單擊廣度優(yōu)先遍歷按鈕，實現(xiàn)圖的鄰接矩陣按照廣度優(yōu)先搜索遍歷并顯示遍歷結(jié)果，如圖8所示。圖8

27、單擊廣度優(yōu)先遍歷按鈕后的界面單擊清空按鈕后，對話框的編輯框內(nèi)容全部置零，如圖9所示。圖8 單擊清空按鈕后的界面單擊退出按鈕后，程序能夠正常實現(xiàn)退出。結(jié) 論本次課程設(shè)計作為編寫Windows程序的初步嘗試，能夠?qū)崿F(xiàn)程序的主要功能，可以說是取得了成功，然而好的程序絕不僅僅是只有功能性這一個指標，本此編寫的MFC程序雖然能實現(xiàn)所需功能，但從面向?qū)ο蟪绦蛟O(shè)計理念和圖形界面設(shè)計要求來說，尚存在不足，程序員可以此為例多加實踐，達到能熟練掌握的效果。MFC為Windows應(yīng)用程序開發(fā)者提供了一種快速開發(fā)的工具，尤其是MFC中提供的多種標準控件，使得開發(fā)者不再將過多的心思花在界面代碼編寫上，而將更多的精力投入到應(yīng)用程序的