數據結構——圖（3）——深度優先搜索算法（DFS）思想

時間 2021-01-19 標籤查找深度優先圖遍歷

圖的遍歷

圖由頂點及其邊組成，圖的遍歷主要分爲兩種：

遍歷所有頂點
遍歷所有邊

我們只討論第一種情況，即不重複的列出所有的頂點，主要有兩種策略：深度優先搜索（DFS）,廣度優先搜索（BFS）

爲了使深度和廣度優先搜索的實現算法的機制更容易理解，假設提供了一個名爲visit的函數，它負責處理每個單獨節點所需的任何處理。因此，遍歷的目的是按照確定的連接順序在每個節點上調用且僅調用一次該函數。因爲圖形通常具有前往相同節點的許多不同路徑，所以確保遍歷算法不會多次訪問同一節點我們需要額外的變量來跟蹤已經訪問過哪些節點。爲此，接下來的兩個部分中的實現定義了一組名爲visited的節點，以跟蹤已經處理的節點。

visit（） //對節點進行相應的操作
visited //標記已訪問過的節點，可以用vector或者set，棧存儲都可以，這裏我們使用set來存儲
foreach(A in B) 在A中搜索符合條件B的元素（遍歷）

深度優先搜索（Depth-first search）

遍歷圖的深度優先策略類似於樹的前序遍歷，並具有相同的遞歸結構。唯一的複雜因素是圖表可以包含環。因此，必須跟蹤已經訪問過的節點。
下面的代碼實現的是從某個特定的節點出發進行的深度優先搜索。

/*
*數據結構 node
*說明：節點的數據結構、
/*
struct Node {
	string name; //節點名稱
	set<Arc *> arcs; //該節點的邊的集合
};
/*
*結構：Arc
*說明：邊的數據結構
*/
struct Arc {
	Node *start; //即從哪個節點出發
	Node *finish; //即指向哪個節點
	double cost;//邊的權重
};


* 函數 ：depthFirstSearch
* 用法: depthFirstSearch(node);
* ------------------------------
* 用指定的節點來初始化DFS的起始節點
*/
void depthFirstSearch(Node *node) {
	Set<Node *> visited;
	visitUsingDFS(node, visited);
}
/*
* 函數: visitUsingDFS
* 用法: visitUsingDFS(node, visited);
* ------------------------------------
* 從特定的節點執行DFS ，並避免重複遍歷相關節點
*/
void visitUsingDFS(Node *node, set<Node *> & visited) {
//如果在visited集合中存在該節點，說明爲simple case，直接返回
	if (visited.contains(node)) return; 
	//否則
	visit(node);//對該節點進行相應操作
	visited.add(node);//將該節點添加到visited集合中
	foreach (Arc *arc in node->arcs) {
	//對每一個節點遞歸調用DFS算法
		visitUsingDFS(arc->finish, visited);
	}
}

DFS的具體過程

下面用一個實例來體會一下DFS的具體過程。還是上次的那張圖

節點被繪製爲空心圓圈以指示它們尚未被訪問。隨着算法的進行，這些圓圈中的每一個都將標有記錄處理該節點的順序的數字。
對depthFirstSearch函數本身的調用會創建一個空的set集合，然後將控制權移交給遞歸的visitUsingDFS函數。假設我們的算法從節點San Francisco處開始，該節點記錄在圖中，如下所示：

對於該節點對應的每一條弧，都遞歸執行DFS算法。

foreach (Arc *arc in node->arcs) {
	visitUsingDFS(arc->finish, visited);
}

這些調用發生的順序取決於foreach逐步遍歷弧的順序。假設foreach按字母順序處理節點，因此優點選擇的是Dallas節點，循環的第一個循環調用visitUsingDFS和Dallas節點，所以會像下圖那樣：
根據我們的代碼，我們必須在San Francisco尋找其他路徑時，完成對Dallas節點的DFS調用。因此根據我們假設的優先訪問規則，下一個要訪問的節點就是Atlanta

深度優先搜索算法的總體效果是在回溯之前儘可能地探索圖中的單個路徑以完成對更高級別的路徑的探索。
因此對於Atlanta節點而言，有兩個節點相鄰，我們根據字母表的優先，選擇Chicago節點。（因爲此時的Dallas已經被標記，不在作爲節點選擇參考的對象）。以此類推：
然而，當程序走到Denver節點時，發現已經沒有可以走的路了，因爲周圍的節點都被標記過，那麼只能往後回溯（就是後退），後退的第一個節點是Chicago，顯然情況跟Denver節點一樣，那麼繼續回溯，是Atlanta節點，發現該節點還有一條未被探索的路徑，所以它回溯到Atlanta節點後，選擇了New York節點，繼續執行DFS：
同樣，以此類推，程序執行到Portland，開始回溯，一直到Dallas。（路徑顯然爲8 -> 7 -> 6 -> 5 ->2）.發現Dallas還有未被探索的路徑。於是找到LosAngeles節點，繼續執行DFS。至此，圖中所有的節點都遍歷完畢：

當然我們可以更爲方便的用棧來存放標記的元素，這樣我們可以在回溯的時候，將元素從棧中彈出即可。當棧空時即表明圖的遍歷完成，棧始終不空，表明圖中有一直不能訪問到的點，因爲沒有路徑通過，此時圖爲不連通的。

那麼同樣的對於下面的有向圖，也可以如下進行搜索，如圖
假設從節點A開始用DFS算法進行遍歷，使用棧來存儲標記過的節點，那麼具體如何實現呢？我會在接下來的博文中詳細分析。