C++的DFS和BFS怎么實(shí)現(xiàn)

這篇文章主要講解了“C++的DFS和BFS怎么實(shí)現(xiàn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++的DFS和BFS怎么實(shí)現(xiàn)”吧！

創(chuàng)新互聯(lián)公司專注于山城網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供山城營(yíng)銷型網(wǎng)站建設(shè)，山城網(wǎng)站制作、山城網(wǎng)頁設(shè)計(jì)、山城網(wǎng)站官網(wǎng)定制、成都小程序開發(fā)服務(wù)，打造山城網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供山城網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

DFS和BFS

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

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

#ifndef Graph_H   #define Graph_H    #include    #include    using namespace std;   #include "Graphmem.h"    template <class name, class dist, class mem>   class Network   {   public:   Network() {}   Network(dist maxdist) { data.NoEdge = maxdist; }   ~Network() {}   bool insertV(name v) { return data.insertV(v); }   bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }   name& getV(int n) { return data.getV(n); }   int nextV(int m, int n = -1) { return data.nextV(m, n); }   int vNum() { return data.vNum; }   int eNum() { return data.eNum; }   protected:   bool* visited;   static void print(name v) { cout << v; }   private:   mem data;   };   #endif

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

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

public:   void DFS(void(*visit)(name v) = print)   {   visited = new bool[vNum()];   for (int i = 0; i < vNum(); i++) visited[i] = false;   DFS(0, visit);   delete []visited;   }   protected:   void DFS(int i, void(*visit)(name v) = print)   {   visit(getV(i)); visited[i] = true;   for (int n = nextV(i); n != -1; n = nextV(i, n))   if (!visited[n]) DFS(n, visit);   }   public:   void BFS(int i = 0, void(*visit)(name v) = print)//n沒有越界檢查   {   visited = new bool[vNum()]; queue<int> a; int n;   for (n = 0; n < vNum(); n++) visited[n] = false;   visited[i] = true;   while (i != -1)//這個(gè)判斷可能是無用的   {   visit(getV(i));   for (n = nextV(i); n != -1; n = nextV(i, n))   if (!visited[n]) { a.push(n); visited[n] = true; }   if (a.empty()) break;   i = a.front(); a.pop();   }   delete []visited;   }

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

測(cè)試程序

#include    using namespace std;   #include "Graph.h"   int main()   {   Network<char, int, LinkedList<char, int> > a;   a.insertV('A'); a.insertV('B');   a.insertV('C'); a.insertV('D');   a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);   a.insertE('B', 'D', 3);   cout << "DFS: "; a.DFS(); cout << endl;   cout << "BFS: "; a.BFS(); cout << endl;   return 0;   }

感謝各位的閱讀，以上就是“C++的DFS和BFS怎么實(shí)現(xiàn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)C++的DFS和BFS怎么實(shí)現(xiàn)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

網(wǎng)站題目：C++的DFS和BFS怎么實(shí)現(xiàn)
文章URL：http://bm7419.com/article30/jcecso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、網(wǎng)站導(dǎo)航、品牌網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)公司、網(wǎng)站收錄、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)