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

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

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

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

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

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

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

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

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

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

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

/************************************************************************* 
  > File Name: DFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 圖 */ 
class Graph 
{ 
  int V;                // 頂點(diǎn)數(shù) 
  list<int> *adj;           // 鄰接表 
  void DFSUtil(int v, bool visited[]); // 從頂點(diǎn)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[]) 
{ 
  // 訪問頂點(diǎn)v并輸出 
  visited[v] = true; 
  cout << v << " "; 
 
  list<int>::iterator i; 
 
  for(i=adj[v].begin(); i!=adj[v].end(); ++i) 
    if(!visited[*i])       // 若鄰接點(diǎn)尚未訪問 
      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è)從給定頂點(diǎn)v可以到達(dá)圖的所有頂點(diǎn) 
  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è)從給定頂點(diǎn)可以訪問到圖的所有其他頂點(diǎn)。如果沒有這個(gè)假設(shè)，為了對圖作一個(gè)完整的深度優(yōu)先遍歷，我們需要對每個(gè)頂點(diǎn)調(diào)用DFSUtil()。當(dāng)然那之前需要先檢查頂點(diǎn)是否已經(jīng)訪問過。所以我們只需要修改DFS()函數(shù)部分：

void Graph::DFS() 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 對每個(gè)頂點(diǎn)調(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); 
}

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

三、DFS算法性能分析

1 . 空間復(fù)雜度

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

2 . 時(shí)間復(fù)雜度

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

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

相關(guān)文章

最新評論