在計算機科學領域，搜索算法是解決問題的重要工具，其中深度優先搜索（Depth-First Search，簡稱 DFS）憑借其簡潔高效的特性，在圖論、回溯、拓撲排序等眾多場景中發揮著關鍵作用。無論是 LeetCode 算法題，還是考研計算機專業基礎綜合（408）考試，深度優先搜索都是高頻考點。

深度優先搜索算法核心思路

深度優先搜索的基本思想是沿著一條路徑盡可能深地探索，直到無法繼續或達到目標狀態，然后回溯到上一個節點，繼續探索其他路徑，直至遍歷完所有可達節點。在圖結構或樹結構中，DFS 可以用來遍歷所有節點、尋找路徑、檢測連通性等。

1.1 算法實現方式

DFS 通常有兩種實現方式：遞歸和迭代（借助棧數據結構）。

• 遞歸實現：利用函數調用棧，從起始節點開始，不斷遞歸訪問相鄰節點，當達到邊界條件（如訪問過的節點、無相鄰節點）時回溯。代碼簡潔直觀，但可能因遞歸深度過深導致棧溢出。

• 迭代實現：手動維護一個棧，將起始節點入棧，每次取出棧頂節點，訪問其未訪問過的相鄰節點并將其入棧，直到棧為空。這種方式可避免棧溢出問題，適用于大規模數據。

1.2 算法流程

以圖結構為例，DFS 的基本流程如下：

1. 選擇一個起始節點，標記為已訪問。

1. 從起始節點出發，找到一個未訪問的相鄰節點，將其標記為已訪問，并以該節點為新的起始節點，遞歸執行步驟 2。

1. 當當前節點的所有相鄰節點都已訪問時，回溯到上一個節點，繼續執行步驟 2。

1. 重復步驟 2 和 3，直到所有可達節點都被訪問。

繪制出的 DFS 遞歸實現的流程圖：

為了更直觀地理解，假設我們有如下無向圖：

從節點 A 開始進行 DFS，訪問順序可能為 A -> B -> D -> E -> C（順序不唯一，取決于具體實現）。

LeetCode 例題實戰

例題 1：200. 島嶼數量

給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和 / 或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。

示例 1：

輸入：grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

輸出：1

解題思路：使用 DFS 遍歷二維網格，當遇到'1'時，將其及其相鄰的'1'全部標記為已訪問（可以將'1'改為'0'），每完成一次 DFS，島嶼數量加 1。

public class NumIslands {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {dfs(grid, i, j);count++;}}}return count;}private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {return;}grid[i][j] = '0';dfs(grid, i - 1, j);dfs(grid, i + 1, j);dfs(grid, i, j - 1);dfs(grid, i, j + 1);}}

例題 2：79. 單詞搜索

給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在于網格中，返回 true ；否則，返回 false 。單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中 “相鄰” 單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

示例 1：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

輸出：true

解題思路：從網格中的每個單元格開始進行 DFS，當當前字符與單詞當前字符匹配時，繼續向相鄰單元格遞歸搜索。為避免重復訪問，使用一個布爾數組記錄單元格是否已被訪問。如果找到匹配的路徑，返回true；遍歷完所有單元格仍未找到，則返回false。

public class WordSearch {public boolean exist(char[][] board, String word) {int m = board.length;int n = board[0].length;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (dfs(board, word, 0, i, j, visited)) {return true;}}}return false;}private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) {int m = board.length;int n = board[0].length;if (index == word.length()) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) {return false;}visited[i][j] = true;boolean result = dfs(board, word, index + 1, i - 1, j, visited) ||dfs(board, word, index + 1, i + 1, j, visited) ||dfs(board, word, index + 1, i, j - 1, visited) ||dfs(board, word, index + 1, i, j + 1, visited);visited[i][j] = false;return result;}}

考研 408 例題分析

例題：已知一個無向連通圖的鄰接表存儲結構，編寫算法判斷圖中是否存在回路。

解題思路：利用 DFS 遍歷圖，在遍歷過程中記錄每個節點的前驅節點。當訪問到一個已訪問過的節點，且該節點不是當前節點的前驅節點時，說明存在回路。

import java.util.ArrayList;import java.util.List;class Graph {int V;List<List<Integer>> adj;Graph(int v) {V = v;adj = new ArrayList<>(v);for (int i = 0; i < v; i++) {adj.add(new ArrayList<>());}}void addEdge(int v, int w) {adj.get(v).add(w);adj.get(w).add(v);}boolean isCyclic() {boolean[] visited = new boolean[V];for (int i = 0; i < V; i++) {if (!visited[i]) {if (dfs(i, -1, visited)) {return true;}}}return false;}private boolean dfs(int v, int parent, boolean[] visited) {visited[v] = true;for (int i : adj.get(v)) {if (!visited[i]) {if (dfs(i, v, visited)) {return true;}} else if (i != parent) {return true;}}return false;}}public class CyclicGraph {public static void main(String[] args) {Graph g1 = new Graph(5);g1.addEdge(1, 0);g1.addEdge(0, 2);g1.addEdge(2, 1);g1.addEdge(0, 3);g1.addEdge(3, 4);if (g1.isCyclic()) {System.out.println("Graph contains cycle");} else {System.out.println("Graph does not contain cycle");}Graph g2 = new Graph(3);g2.addEdge(0, 1);g2.addEdge(1, 2);if (g2.isCyclic()) {System.out.println("Graph contains cycle");} else {System.out.println("Graph does not contain cycle");}}}

總結

深度優先搜索算法以其獨特的搜索策略，在解決各類問題中展現出強大的能力。通過 LeetCode 例題和考研 408 真題的實戰演練，我們不僅掌握了 DFS 在不同場景下的應用，還熟悉了其 Java 代碼實現。在實際編程和考研備考中，熟練運用 DFS 算法，能夠有效提升問題解決能力。后續可以進一步研究 DFS 與其他算法的結合應用，探索其在更復雜場景下的優化與拓展。

希望本文能夠幫助讀者更深入地理解深度優先搜索算法，并在實際項目中發揮其優勢。謝謝閱讀！

---

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。