C++深度優先搜刮的完成辦法

C++深度優先搜刮的完成辦法。本站提示廣大學習愛好者：（C++深度優先搜刮的完成辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++深度優先搜刮的完成辦法正文

本文實例講述了圖的遍歷中深度優先搜刮的C++完成辦法，是一種異常主要的算法，詳細完成辦法以下：

起首，圖的遍歷是指從圖中的某一個極點動身，依照某種搜刮辦法沿著圖中的邊對圖中的一切極點拜訪一次且僅拜訪一次。留意到樹是一種特別的圖，所以樹的遍歷現實上也能夠看做是一種特別的圖的遍歷。圖的遍歷重要有兩種算法：廣度優先搜刮（Breadth-First-Search）和深度優先搜刮（Depth-First-Search）。

1、深度優先搜刮（DFS）的算法思惟

深度優先搜刮算法所遵守的搜刮戰略是盡量“深”地搜刮一個圖。它的根本思惟就是：起首拜訪圖中某一路始極點v，然後由v動身，拜訪與v鄰接且未被拜訪的任一極點w1，再拜訪與w1鄰接且未被拜訪的任一極點w2，……反復上述進程。當不克不及再持續向下拜訪時，順次退回到比來被拜訪的極點，若它還有鄰接極點未被拜訪過，則從該點開端持續上述搜刮進程，直到圖中一切極點均被拜訪過為止。

如上圖所示，從極點2開端深度優先遍歷圖，成果為：2，0，1，3。

2、DFS算法完成

和廣度優先搜刮一樣，為了避免極點被屢次拜訪，須要應用一個拜訪標志數組visited[]來標志極點能否曾經被拜訪過。

這裡應用鄰接表表現圖。關於一個有向圖，假定從給定極點可以拜訪到圖的一切其他極點，則DFS遞歸算法的C++代碼完成：

/************************************************************************* 
  > File Name: DFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 圖 */ 
class Graph 
{ 
  int V;                // 極點數 
  list<int> *adj;           // 鄰接表 
  void DFSUtil(int v, bool visited[]); // 從極點v深度優先遍歷 
public: 
  Graph(int V);            // 結構函數 
  void addEdge(int v, int w);     // 向圖中添加邊 
  void DFS(int v);           // 從v開端深度優先遍歷圖 
}; 
 
/* 結構函數 */ 
Graph::Graph(int V) 
{ 
  this->V = V; 
  adj = new list<int>[V]; 
} 
 
/* 添加邊，結構鄰接表 */ 
void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);         // 將w添加到v的鏈表 
} 
 
/* 從v開端深度優先遍歷 */ 
void Graph::DFSUtil(int v, bool visited[]) 
{ 
  // 拜訪極點v並輸入 
  visited[v] = true; 
  cout << v << " "; 
 
  list<int>::iterator i; 
 
  for(i=adj[v].begin(); i!=adj[v].end(); ++i) 
    if(!visited[*i])       // 若鄰接點還沒有拜訪 
      DFSUtil(*i, visited);   // 遞歸 
} 
 
/* 對圖停止深度優先遍歷，挪用遞歸函數DFSUtil() */ 
void Graph::DFS(int v) 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
 
  // 假定從給定極點v可以達到圖的一切極點 
  DFSUtil(v, visited); 
} 
 
/* 測試 */ 
int main() 
{ 
  Graph g(4); 
  g.addEdge(0, 1); 
  g.addEdge(0, 2); 
  g.addEdge(1, 2); 
  g.addEdge(2, 0); 
  g.addEdge(2, 3); 
  g.addEdge(3, 3); 
 
  cout << "Depth First Traversal (starting from vertex 2) \n"; 
  g.DFS(2); 
  cout << endl; 
   
  return 0; 
}

下面的代碼是假定從給定極點可以拜訪到圖的一切其他極點。假如沒有這個假定，為了對圖作一個完全的深度優先遍歷，我們須要對每一個極點挪用DFSUtil()。固然那之前須要先檢討極點能否曾經拜訪過。所以我們只須要修正DFS()函數部門：

void Graph::DFS() 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 對每一個極點挪用DFSUtil()，從0開端 
  for(int i=0; i<V; ++i) 
    if(!visited[i]) 
      DFSUtil(i, visited); 
} 

關於無向圖的深度優先搜刮，只是鄰接表紛歧樣，其他的都是一樣的。我們只須要修正addEdge(v, w)函數：

void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);     // 將w加到v的list 
  adj[w].push_back(v); 
} 

留意：圖的鄰接矩陣表現是獨一的，但關於鄰接表來講，假如邊的輸出順序分歧，生成的鄰接表也分歧。是以，關於統一個圖，基於鄰接矩陣的遍歷所獲得的DFS序列和BFS序列是獨一的，基於鄰接表的遍歷所獲得的DFS序列和BFS序列是不惟一的。

3、DFS算法機能剖析

1 . 空間龐雜度

DFS算法是一個遞歸算法，須要借助一個遞歸任務棧，故它的空間龐雜度為O(|V|)。

2 . 時光龐雜度

當以鄰接表存儲時，時光龐雜度為O(|V|+|E|)。

當以鄰接矩陣存儲時，時光龐雜度為O(|V|^2)。