C++深度優(yōu)先搜索的實現(xiàn)方法
本文實例講述了圖的遍歷中深度優(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，……重復上述過程。當不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點均被訪問過為止。
如上圖所示，從頂點2開始深度優(yōu)先遍歷圖，結果為：2，0，1，3。
二、DFS算法實現(xiàn)
和廣度優(yōu)先搜索一樣，為了防止頂點被多次訪問，需要使用一個訪問標記數(shù)組visited[]來標記頂點是否已經(jīng)被訪問過。
這里使用鄰接表表示圖。對于一個有向圖，假設從給定頂點可以訪問到圖的所有其他頂點，則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); // 構造函數(shù)
void addEdge(int v, int w); // 向圖中添加邊
void DFS(int v); // 從v開始深度優(yōu)先遍歷圖
};
/* 構造函數(shù) */
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開始深度優(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); // 遞歸
}
/* 對圖進行深度優(yōu)先遍歷，調用遞歸函數(shù)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;
}
上面的代碼是假設從給定頂點可以訪問到圖的所有其他頂點。如果沒有這個假設，為了對圖作一個完整的深度優(yōu)先遍歷，我們需要對每個頂點調用DFSUtil()。當然那之前需要先檢查頂點是否已經(jīng)訪問過。所以我們只需要修改DFS()函數(shù)部分：
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);
}
對于無向圖的深度優(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 . 空間復雜度
DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，故它的空間復雜度為O(|V|)。
2 . 時間復雜度
當以鄰接表存儲時，時間復雜度為O(|V|+|E|)。
當以鄰接矩陣存儲時，時間復雜度為O(|V|^2)。
相關文章
這篇文章主要為大家詳細介紹了Qt中QList與QLinkedList類的常用方法，文中的示例代碼講解詳細，對我們學習Qt有一定的幫助，需要的可以參考一下2022-12-12
C++中類的成員函數(shù)及內聯(lián)函數(shù)使用及說明
這篇文章主要介紹了C++中類的成員函數(shù)及內聯(lián)函數(shù)使用及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
C++實現(xiàn)LeetCode(164.求最大間距)
這篇文章主要介紹了C++實現(xiàn)LeetCode(164.求最大間距),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
OpenCV獲取圖像中直線上的數(shù)據(jù)具體流程
對圖像進行處理時，經(jīng)常會有這類需求：客戶想要提取出圖像中某條直線或者ROI區(qū)域內的感興趣數(shù)據(jù)，進行重點關注，怎么操作呢，下面小編通過實例代碼介紹下OpenCV獲取圖像中直線上的數(shù)據(jù)，一起看看吧2021-11-11
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)圖書管理信息系統(tǒng)設計與實現(xiàn)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C語言中的字符串數(shù)據(jù)在C中的存儲方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
在C#中要說類默認給我們定義的特殊成員函數(shù)，莫過于構造函數(shù)，但在?C++?中這樣的特殊函數(shù)高達6種，本文就整合一下和大家一起聊一聊2022-07-07
歸并排序遵循分治法的思想：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。分治模式在每層遞歸時都有三個步驟：分解、解決、合并。歸并排序完全遵循該模式。2017-05-05
C++是面向對象編程的,這也是C++與C語言的最大區(qū)別,而類和對象就是C++面向對象的基礎,下面這篇文章主要給大家介紹了關于C++初階教程之類和對象的相關資料,需要的朋友可以參考下2022-02-02
所謂并發(fā)編程是指在一臺處理器上“同時”處理多個任務。并發(fā)是在同一實體上的多個事件。多個事件在同一時間間隔發(fā)生，下面我們根據(jù)樣例來理解2022-04-04