日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
六講貫通C++圖的應(yīng)用之二 DFS和BFS

筆者從基本儲(chǔ)存方法、DFS和BFS、無(wú)向圖、最小生成樹(shù)、最短路徑以及活動(dòng)網(wǎng)絡(luò)(AOV、AOE)六個(gè)方面詳細(xì)介紹C++圖的應(yīng)用。上篇文章我們介紹了基本存儲(chǔ)方法，這篇介紹DFS和BFS。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、重慶小程序開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了隆林免費(fèi)建站歡迎大家使用！

DFS和BFS

對(duì)于非線性的結(jié)構(gòu)，遍歷都會(huì)首先成為一個(gè)問(wèn)題。和二叉樹(shù)的遍歷一樣，圖也有深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)兩種。不同的是，圖中每個(gè)頂點(diǎn)沒(méi)有了祖先和子孫的關(guān)系，因此，前序、中序、后序不再有意義了。仿照二叉樹(shù)的遍歷，很容易就能完成DFS和BFS，只是要注意圖中可能有回路，因此，必須對(duì)訪問(wèn)過(guò)的頂點(diǎn)做標(biāo)記。

最基本的有向帶權(quán)網(wǎng)

 
 
 
      
  
  
  1. #ifndef Graph_H   
    2.   
  
  
  2. #define Graph_H   
    3.   
  
  
  3.  
    4.   
  
  
  4. #include     
    5.   
  
  
  5. #include     
    6.   
  
  
  6. using namespace std;   
    7.   
  
  
  7. #include "Graphmem.h"   
    8.   
  
  
  8.  
    9.   
  
  
  9. template    
    10.   
  
  
  10. class Network   
    11.   
  
  
  11. {   
    12.   
  
  
  12. public:   
    13.   
  
  
  13. Network() {}   
    14.   
  
  
  14. Network(dist maxdist) { data.NoEdge = maxdist; }   
    15.   
  
  
  15. ~Network() {}   
    16.   
  
  
  16. bool insertV(name v) { return data.insertV(v); }   
    17.   
  
  
  17. bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }   
    18.   
  
  
  18. name& getV(int n) { return data.getV(n); }   
    19.   
  
  
  19. int nextV(int m, int n = -1) { return data.nextV(m, n); }   
    20.   
  
  
  20. int vNum() { return data.vNum; }   
    21.   
  
  
  21. int eNum() { return data.eNum; }   
    22.   
  
  
  22. protected:   
    23.   
  
  
  23. bool* visited;   
    24.   
  
  
  24. static void print(name v) { cout << v; }   
    25.   
  
  
  25. private:   
    26.   
  
  
  26. mem data;   
    27.   
  
  
  27. };   
    28.   
  
  
  28. #endif  
    29.

你可以看到，這是在以mem方式儲(chǔ)存的data上面加了一層外殼。在圖這里，邏輯上分有向、無(wú)向，帶權(quán)、不帶權(quán);儲(chǔ)存結(jié)構(gòu)上有鄰接矩陣和鄰接表。也就是說(shuō)分開(kāi)來(lái)有8個(gè)類。為了***限度的復(fù)用代碼，繼承關(guān)系就非常復(fù)雜了。但是，多重繼承是件很討厭的事，什么覆蓋啊，還有什么虛擬繼承，我可不想花大量篇幅講語(yǔ)言特性。于是，我將儲(chǔ)存方式作為第三個(gè)模板參數(shù)，這樣一來(lái)就省得涉及虛擬繼承了，只是這樣一來(lái)這個(gè)Network的實(shí)例化就很麻煩了，不過(guò)這可以通過(guò)typedef或者外殼類來(lái)解決，我就不寫(xiě)了。反正只是為了讓大家明白，真正要用的時(shí)候，***是寫(xiě)專門的類，比如無(wú)向無(wú)權(quán)鄰接矩陣圖，不要搞的繼承關(guān)系亂七八糟。

DFS和BFS的實(shí)現(xiàn)

 
 
 
      
  
  
  1. public:   
    2.   
  
  
  2. void DFS(void(*visit)(name v) = print)   
    3.   
  
  
  3. {   
    4.   
  
  
  4. visited = new bool[vNum()];   
    5.   
  
  
  5. for (int i = 0; i < vNum(); i++) visited[i] = false;   
    6.   
  
  
  6. DFS(0, visit);   
    7.   
  
  
  7. delete []visited;   
    8.   
  
  
  8. }   
    9.   
  
  
  9. protected:   
    10.   
  
  
  10. void DFS(int i, void(*visit)(name v) = print)   
    11.   
  
  
  11. {   
    12.   
  
  
  12. visit(getV(i)); visited[i] = true;   
    13.   
  
  
  13. for (int n = nextV(i); n != -1; n = nextV(i, n))   
    14.   
  
  
  14. if (!visited[n]) DFS(n, visit);   
    15.   
  
  
  15. }   
    16.   
  
  
  16. public:   
    17.   
  
  
  17. void BFS(int i = 0, void(*visit)(name v) = print)//n沒(méi)有越界檢查   
    18.   
  
  
  18. {   
    19.   
  
  
  19. visited = new bool[vNum()]; queue a; int n;   
    20.   
  
  
  20. for (n = 0; n < vNum(); n++) visited[n] = false;   
    21.   
  
  
  21. visited[i] = true;   
    22.   
  
  
  22. while (i != -1)//這個(gè)判斷可能是無(wú)用的   
    23.   
  
  
  23. {   
    24.   
  
  
  24. visit(getV(i));   
    25.   
  
  
  25. for (n = nextV(i); n != -1; n = nextV(i, n))   
    26.   
  
  
  26. if (!visited[n]) { a.push(n); visited[n] = true; }   
    27.   
  
  
  27. if (a.empty()) break;   
    28.   
  
  
  28. i = a.front(); a.pop();   
    29.   
  
  
  29. }   
    30.   
  
  
  30. delete []visited;   
    31.   
  
  
  31. }  
    32.

DFS和BFS函數(shù)很難寫(xiě)得像樹(shù)的遍歷方法那么通用，這在后面就會(huì)看到，雖然我們使用了DFS和BFS的思想，但是上面的函數(shù)卻不能直接使用。因?yàn)闃?shù)的信息主要在節(jié)點(diǎn)上，而圖的邊上還有信息。

測(cè)試程序

 
 
 
      
  
  
  1. #include     
    2.   
  
  
  2. using namespace std;   
    3.   
  
  
  3. #include "Graph.h"   
    4.   
  
  
  4. int main()   
    5.   
  
  
  5. {   
    6.   
  
  
  6. Network > a;   
    7.   
  
  
  7. a.insertV('A'); a.insertV('B');   
    8.   
  
  
  8. a.insertV('C'); a.insertV('D');   
    9.   
  
  
  9. a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);   
    10.   
  
  
  10. a.insertE('B', 'D', 3);   
    11.   
  
  
  11. cout << "DFS: "; a.DFS(); cout << endl;   
    12.   
  
  
  12. cout << "BFS: "; a.BFS(); cout << endl;   
    13.   
  
  
  13. return 0;   
    14.   
  
  
  14. }  
    15.

老實(shí)說(shuō)，這個(gè)類用起來(lái)真的不是很方便。不過(guò)能說(shuō)明問(wèn)題就好。

【編輯推薦】

  1. 經(jīng)典四講貫通C++排序之一 插入排序
  2. c++編程常用工具
  3. 給C++初學(xué)者的50個(gè)忠告
  4. c++最基礎(chǔ)的20條規(guī)則
  5. 程序員必看 c++筆試題匯總

網(wǎng)站名稱：六講貫通C++圖的應(yīng)用之二 DFS和BFS
URL標(biāo)題：http://www.5511xx.com/article/cdjdodo.html