如何進行數據結構之圖的深度優先搜索

# 如何進行數據結構之圖的深度優先搜索

## 一、深度優先搜索（DFS）概述

深度優先搜索（Depth-First Search, DFS）是圖遍歷算法中最經典的算法之一，其核心思想是"一條路走到黑，再回頭探索"。該算法會盡可能深地探索圖的分支，直到當前分支所有節點都被訪問過，再回溯到上一個節點繼續探索未訪問的分支。

### 1.1 基本特點
- 后進先出的探索方式（天然適合棧結構實現）
- 時間復雜度：O(V+E)（V為頂點數，E為邊數）
- 空間復雜度：O(V)（最壞情況下需要存儲整條路徑）

## 二、DFS算法實現步驟

### 2.1 遞歸實現（最直觀的方式）
```python
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)  # 處理當前節點
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

2.2 非遞歸實現（顯式使用棧）

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)  # 處理當前節點
            
            # 注意壓棧順序與遞歸順序相反
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

三、關鍵問題與解決方案

3.1 避免重復訪問

必須使用訪問標記（visited集合）來防止： - 無向圖中的來回震蕩 - 有向圖中的環路導致的無限循環

3.2 遍歷順序控制

根據業務需求選擇鄰接節點的訪問順序： - 升序/降序排列（影響生成樹形態） - 加權圖中的優先級處理

3.3 非連通圖處理

def dfs_disconnected(graph):
    visited = set()
    for node in graph:
        if node not in visited:
            dfs_recursive(graph, node, visited)

四、DFS的典型應用場景

4.1 路徑查找問題

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath:
                return newpath
    return None

4.2 拓撲排序（有向無環圖）

def topological_sort(graph):
    visited = set()
    result = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # 后序添加
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return result[::-1]  # 反轉結果

4.3 檢測環路

def has_cycle(graph):
    visited = set()
    recursion_stack = set()
    
    def dfs(node):
        visited.add(node)
        recursion_stack.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True
        recursion_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

五、性能優化技巧

5.1 剪枝策略

• 提前終止條件（如找到目標時立即返回）
• 可行性判斷（放棄不可能的分支）

5.2 迭代深化搜索（IDS）

結合BFS和DFS優點，適用于狀態空間未知的情況：

def ids(graph, start, max_depth):
    for depth in range(max_depth):
        visited = set()
        if dls(graph, start, depth, visited):
            return True
    return False

def dls(graph, node, depth, visited):
    if depth == 0 and node == target:
        return True
    if depth > 0:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dls(graph, neighbor, depth-1, visited):
                    return True
    return False

六、對比廣度優先搜索（BFS）

七、總結

深度優先搜索通過其”縱向深入”的探索方式，成為解決圖論問題的利器。掌握DFS需要理解： 1. 遞歸調用棧的本質 2. 回溯機制的應用場景 3. 剪枝優化的實際價值

建議讀者通過LeetCode典型題目（如200.島嶼數量、207.課程表等）進行實踐訓練，加深對DFS的理解和應用能力。 “`

注：本文實際約1100字，包含代碼示例、對比表格和結構化說明?？筛鶕枰鰷p代碼示例或添加可視化圖示（如DFS遍歷過程的樹形圖）。