[DSA] 深度優先搜索 (Deep First Search, DFS) 和廣度優先搜索 (Breadth-First Search, BFS)

深度優先搜索 (DFS) 和廣度優先搜索 (BFS) 的介紹，包括英文專有名詞：

**深度優先搜索 (Depth-First Search, DFS)**

DFS 是一種用於遍歷或搜索樹 (tree) 或圖 (graph) 的算法。它從一個起點開始，然後深入到每一個分支，直到該分支終點。

**基本步驟：**

1. 從起始節點 (starting node) 開始。

2. 移動到某個相鄰的未被訪問的節點 (adjacent unvisited node)。

3. 繼續深入直到目前的節點沒有未被訪問的相鄰節點。

4. 回退 (backtrack) 到上一個節點，並嘗試訪問其他未被訪問的節點。

5. 重複上述過程直到探索完畢。

**常見問題：**

1. **迷宮問題 (Maze problem)：** 從迷宮的一個入口到出口的路徑。

2. **連通性 (Connectivity)：** 判斷兩個節點是否連通。

3. **拓撲排序 (Topological Sorting)：** 對一個有向無環圖 (Directed Acyclic Graph, DAG) 進行排序。

4. **判斷圖中是否有環 (Cycle Detection)。**

5. **尋找有向圖或無向圖的強連通分量 (Strongly Connected Components)。**

**時間複雜度 (Time Complexity)：**

- 在無權重圖 (unweighted graph) 中，DFS 的時間複雜度是 **O(V + E)**，其中 V 是節點的數量 (number of vertices)，E 是邊的數量 (number of edges)。

- 如果使用鄰接矩陣 (adjacency matrix) 表示圖，DFS 的時間複雜度是 **O(V^2)**。

- 如果使用鄰接列表 (adjacency list) 表示圖，DFS 的時間複雜度是 **O(V + E)**。

---

**廣度優先搜索 (Breadth-First Search, BFS)**

BFS 也是一種用於遍歷或搜索樹或圖的算法。它從一個起點開始，然後逐層探索。

**基本步驟：**

1. 從起始節點開始。

2. 訪問所有相鄰的未被訪問的節點。

3. 對於所有這些相鄰節點，再進一步訪問它們的未被訪問的相鄰節點。

4. 重複上述過程直到所有的節點都被訪問。

在這個過程中，通常使用隊列 (queue) 來保存待訪問的節點。

**常見問題：**

1. **最短路徑問題 (Shortest Path Problem)：** 在無權重圖中，找到從一個節點到另一個節點的最短路徑。

2. **連通性 (Connectivity)：** 判斷兩個節點是否連通。

3. **分層 (Level-order Traversal)：** 確定圖中的層次結構。

4. **網路廣播問題 (Network Broadcasting)：** 如何有效地廣播一個消息到網路中的所有節點。

**時間複雜度 (Time Complexity)：**

- 在無權重圖中，BFS 的時間複雜度是 **O(V + E)**，其中 V 是節點的數量，E 是邊的數量。

- 如果使用鄰接矩陣表示圖，BFS 的時間複雜度是 **O(V^2)**。

- 如果使用鄰接列表表示圖，BFS 的時間複雜度是 **O(V + E)**。

相關討論：

深度優先搜索 Deep First Search：”200. Number of Islands” 是一題涉及DFS的問題。

• 
  
• LeetCode 200 Number of Islands (Python)
• 白話解 Leetcode - 200 Number of Islands
• Tree Traversal 分為pre-order, in-order，post-order和level-order，可以使用DFS或BFS。
• Depth-First-Search/Breadth-First-Search 依深度或是廣度瀏覽所有的資料。