深度優先搜尋演算法 (DFS)

7.1 DFS 演算法的工作原理

深度優先搜尋 (Depth-First Search, DFS) 是一種圖形遍歷或搜尋演算法。它從起始節點開始，深入圖形，直到到達一個沒有未訪問的鄰居的節點，然後回溯並從其他節點繼續過程。

演算法步驟：

1. 從選定的起始節點開始，並將其標記為已訪問。
2. 探索第一個未訪問的鄰近節點。
3. 對該鄰居重複步驟 1 和 2。
4. 如果當前節點的所有鄰居都已訪問，則回溯到前一個節點，然後繼續過程。
5. 該過程持續重複，直到從起始節點到達的所有節點都被訪問為止。

視覺化：

DFS 的時間和空間複雜度：

時間複雜度：

O(V + E)，其中 V 是頂點數量，E 是邊數量。

每個節點和每條邊僅訪問一次。

空間複雜度：

O(V)，因為使用了調用棧或顯式棧來存儲頂點，以及用於存儲狀態（已訪問節點）的數組。

7.2 使用遞歸實現 DFS

我們先用遞歸實現 DFS —— 代碼會很簡潔。

遞歸實現 DFS：

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 處理節點
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 使用棧實現 DFS

不使用遞歸的代碼會稍長一點，因為我們需要另外保存已訪問節點的列表。

迭代實現 DFS（使用棧）：

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 處理節點
        
            for neighbor in reversed(graph[vertex]):  # 反向順序以保證正確的遍歷順序
                if neighbor not in visited:
                    stack.append(neighbor)
        
# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 使用 DFS 解決的問題範例

使用 DFS 解決的經典問題範例：

1. 迷宮尋路：

用於從起點到終點的迷宮導航。

應用：

在電子遊戲和機器人技術中用於迷宮和複雜空間的導航。

2. 檢查圖的連通性：

檢查圖是否為連通圖（即任意兩個頂點之間是否存在路徑）。

應用：

在網路分析中檢查網路的連通性。

3. 拓撲排序：

用於對有向無環圖 (DAG) 中的頂點進行排序，使得對於任意邊 (u, v)，頂點 u 在頂點 v 之前。

應用：

在編譯器中用於排序依賴和任務。

4. 圖中循環的檢測：

檢查圖中是否包含循環。

應用：

在依賴分析中用於檢測循環依賴。

5. 迷宮生成：

使用 DFS 生成隨機迷宮。

應用：

在遊戲和娛樂應用中創建迷宮。