千年殇,有声小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

六講貫通C++圖的應(yīng)用之二 DFS和BFS

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

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

DFS和BFS

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

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

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

DFS和BFS的實現(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 a; int n;     
  
  for (n = 0; n < vNum(); n++) visited[n] = false;     
  
  visited[i] = true;     
  
  while (i != -1)//這個判斷可能是無用的     
  
  {     
  
  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ù)很難寫得像樹的遍歷方法那么通用，這在后面就會看到，雖然我們使用了DFS和BFS的思想，但是上面的函數(shù)卻不能直接使用。因為樹的信息主要在節(jié)點上，而圖的邊上還有信息。

測試程序

 
 
   
  
  #include       
  
  using namespace std;     
  
  #include "Graph.h"     
  
  int main()     
  
  {     
  
  Network > 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;     
  
  }

老實說，這個類用起來真的不是很方便。不過能說明問題就好。

【編輯推薦】

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

分享名稱：六講貫通C++圖的應(yīng)用之二 DFS和BFS
網(wǎng)頁鏈接：http://m.fisionsoft.com.cn/article/cdjdodo.html

新聞中心

其他資訊