欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++深度優(yōu)先搜索的實現(xiàn)方法

 更新時間：2014年08月14日 14:53:39   投稿：shichen2014  
這篇文章主要介紹了C++深度優(yōu)先搜索的實現(xiàn)方法,是數(shù)據(jù)結(jié)構(gòu)中非常重要的一種算法,需要的朋友可以參考下

本文實例講述了圖的遍歷中深度優(yōu)先搜索的C++實現(xiàn)方法，是一種非常重要的算法，具體實現(xiàn)方法如下：

首先，圖的遍歷是指從圖中的某一個頂點出發(fā)，按照某種搜索方法沿著圖中的邊對圖中的所有頂點訪問一次且僅訪問一次。注意到樹是一種特殊的圖，所以樹的遍歷實際上也可以看作是一種特殊的圖的遍歷。圖的遍歷主要有兩種算法：廣度優(yōu)先搜索（Breadth-First-Search）和深度優(yōu)先搜索（Depth-First-Search）。

一、深度優(yōu)先搜索（DFS）的算法思想

深度優(yōu)先搜索算法所遵循的搜索策略是盡可能“深”地搜索一個圖。它的基本思想就是：首先訪問圖中某一起始頂點v，然后由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點w1，再訪問與w1鄰接且未被訪問的任一頂點w2，……重復(fù)上述過程。當(dāng)不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點均被訪問過為止。

如上圖所示，從頂點2開始深度優(yōu)先遍歷圖，結(jié)果為：2，0，1，3。

二、DFS算法實現(xiàn)

和廣度優(yōu)先搜索一樣，為了防止頂點被多次訪問，需要使用一個訪問標(biāo)記數(shù)組visited[]來標(biāo)記頂點是否已經(jīng)被訪問過。

這里使用鄰接表表示圖。對于一個有向圖，假設(shè)從給定頂點可以訪問到圖的所有其他頂點，則DFS遞歸算法的C++代碼實現(xiàn)：

/************************************************************************* 
  > File Name: DFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 圖 */ 
class Graph 
{ 
  int V;                // 頂點數(shù) 
  list<int> *adj;           // 鄰接表 
  void DFSUtil(int v, bool visited[]); // 從頂點v深度優(yōu)先遍歷 
public: 
  Graph(int V);            // 構(gòu)造函數(shù) 
  void addEdge(int v, int w);     // 向圖中添加邊 
  void DFS(int v);           // 從v開始深度優(yōu)先遍歷圖 
}; 
 
/* 構(gòu)造函數(shù) */ 
Graph::Graph(int V) 
{ 
  this->V = V; 
  adj = new list<int>[V]; 
} 
 
/* 添加邊，構(gòu)造鄰接表 */ 
void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);         // 將w添加到v的鏈表 
} 
 
/* 從v開始深度優(yōu)先遍歷 */ 
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);   // 遞歸 
} 
 
/* 對圖進(jìn)行深度優(yōu)先遍歷，調(diào)用遞歸函數(shù)DFSUtil() */ 
void Graph::DFS(int v) 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
 
  // 假設(shè)從給定頂點v可以到達(dá)圖的所有頂點 
  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; 
}

上面的代碼是假設(shè)從給定頂點可以訪問到圖的所有其他頂點。如果沒有這個假設(shè)，為了對圖作一個完整的深度優(yōu)先遍歷，我們需要對每個頂點調(diào)用DFSUtil()。當(dāng)然那之前需要先檢查頂點是否已經(jīng)訪問過。所以我們只需要修改DFS()函數(shù)部分：

void Graph::DFS() 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 對每個頂點調(diào)用DFSUtil()，從0開始 
  for(int i=0; i<V; ++i) 
    if(!visited[i]) 
      DFSUtil(i, visited); 
}

對于無向圖的深度優(yōu)先搜索，只是鄰接表不一樣，其他的都是一樣的。我們只需要修改addEdge(v, w)函數(shù)：

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

注意：圖的鄰接矩陣表示是唯一的，但對于鄰接表來說，如果邊的輸入次序不同，生成的鄰接表也不同。因此，對于同一個圖，基于鄰接矩陣的遍歷所得到的DFS序列和BFS序列是唯一的，基于鄰接表的遍歷所得到的DFS序列和BFS序列是不唯一的。

三、DFS算法性能分析

1 . 空間復(fù)雜度

DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，故它的空間復(fù)雜度為O(|V|)。

2 . 時間復(fù)雜度

當(dāng)以鄰接表存儲時，時間復(fù)雜度為O(|V|+|E|)。

當(dāng)以鄰接矩陣存儲時，時間復(fù)雜度為O(|V|^2)。

相關(guān)文章

最新評論