算法系列之搜索算法-深度優先搜索DFS
作者：修己xj
DFS 是一種非常重要的圖遍歷算法，適用于許多場景。遞歸實現簡單直觀，但可能會受到棧深度的限制；迭代實現則避免了這個問題，但代碼稍復雜一些。根據具體需求選擇合適的實現方式。
隨著每年"金三銀四"招聘季的到來，許多求職者開始積極備戰面試。在眾多面試環節中，機試往往是不可或缺的一環，而算法能力更是機試考核的重點。為此，我們特別推出算法系列文章，幫助大家系統復習算法知識。今天，我們將首先探討搜索算法中的重要內容——深度度優先搜索（DFS）。
圖的介紹
圖(Graph)是一種非線性的數據結構，由頂點（Vertex）和邊（Edge）組成。如下圖所示
分類如下：
- 無向圖（Undirected Graph）：邊沒有方向，表示雙向關系。
- 有向圖（Directed Graph）：邊有方向，表示單向關系。
- 加權圖（Weighted Graph）：邊帶有權重。
- 無權圖（Unweighted Graph）：邊沒有權重。
深度優先搜索（DFS, Depth-First Search）
深度優先搜索和廣度優先搜索一樣，都是對圖進行搜索的算法，目的也都是從起點開始搜索，直到到達頂點。深度優先搜索會沿著一條路徑不斷的往下搜索，直到不能夠在繼續為止，然后在折返，開始搜索下一條候補路徑。
DFS 可以借助于?；蛘邅韺崿F。棧具有”后進先出（LIFO）”特性，可以是有?；蛘哌f歸來實現遍歷。其實現步驟如下：
- 訪問節點：從起始節點開始，訪問當前節點。
- 遞歸
- 遞歸訪問鄰居：對于當前節點的每一個未訪問過的鄰居節點，遞歸地調用 DFS。
- 回溯：當沒有未訪問的鄰居時，回溯到上一個節點，繼續搜索其他路徑。
- 棧
- 使用 Stack 來模擬遞歸過程，每次從棧中彈出一個節點并訪問它，然后將未訪問的鄰居節點壓入棧中。
示例代碼如下：
/**
* 深度優先搜索示例
*/
public class DFSExample {
// 定義圖的節點類
static class Node {
int value;
List< Node> neighbors;
public Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
// 添加鄰接節點
public void addNeighbor( Node neighbor) {
this.neighbors.add(neighbor);
}
}
/**
* 方式一 ：棧實現
* dfs 函數
* @param startNode
*/
public static void dfs( Node startNode) {
if(startNode == null ) return;
// 使用隊列存儲待訪問的節點
Stack<Node> stack = new Stack<>();
// 使用HashSet記錄已訪問的節點
Set<Node> visited = new HashSet<>();
// 將起點加入棧并標記為已訪問
stack.push(startNode);
visited.add(startNode);
// 遍歷棧
while (!stack.isEmpty()){
Node currentNode = stack.pop();
System.out.println(currentNode.value);
// 遍歷當前節點的所有鄰接節點
for (Node neighbor : currentNode.neighbors) {
// 如果鄰接節點未被訪問，則加入棧并標記為已訪問
if (!visited.contains(neighbor)) {
stack.add(neighbor);
visited.add(neighbor);
}
}
}
}
//方式二：遞歸實現
public static void sec( Node currentNode,Set<Node> visited) {
// 標記當前節點為已訪問
visited.add(currentNode);
System.out.println(currentNode.value);
// 遞歸訪問所有未訪問的鄰居節點
for (Node neighbor : currentNode.neighbors) {
if (!visited.contains(neighbor))
sec(neighbor, visited);
}
}
/**
*
* @param args
*/
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
node1.addNeighbor(node2);
node1.addNeighbor(node3);
node1.addNeighbor(node5);
node2.addNeighbor(node1);
node2.addNeighbor(node3);
node2.addNeighbor(node5);
node3.addNeighbor(node1);
node3.addNeighbor(node2);
node3.addNeighbor(node4);
node3.addNeighbor(node6);
node4.addNeighbor(node3);
node4.addNeighbor(node6);
node5.addNeighbor(node2);
node5.addNeighbor(node6);
node6.addNeighbor(node3);
node6.addNeighbor(node4);
node6.addNeighbor(node5);
//棧實現
dfs(node1);
System.out.println("+++++++++遞歸實現++++++++++++");
//遞歸實現
Set< Node> visited = new HashSet<>();
sec(node1,visited);
}
}DFS的特點
- 時間復雜度：O(V+E)
- 空間復雜度：O(V)
- 適用場景：連通性檢測、路徑查找、迷宮求解
DFS 示例題
以下列舉了一些機試題
廣播服務器
題目描述：給定一個大小為 N×N 的二維矩陣 matrix，表示 N 個服務器之間的連接情況。matrix[i][j] = 1 表示服務器i 和 j 直接連接，matrix[i][j] = 0 表示不直接連接。計算初始需要給幾臺服務器廣播，才能使每個服務器都收到廣播。 輸入：N 行，每行 N 個數字（0 或 1），表示 N×N 的二維矩陣。 輸出：需要廣播的服務器的數量。
示例一： 輸入：
1 0 0
0 1 0
0 0 1
輸出：3
示例二： 輸入：
1 1
1 1
輸出：1
public class DFSServer {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] firstLine = scanner.nextLine().split(" ");
int n = firstLine.length;
//初始化二維數組
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
String[] line = i==0 ? firstLine:scanner.nextLine().split(" ");
for (int j = 0; j < n; j++) {
matrix[i][j] = Integer.parseInt(line[j]);
}
}
//初始化標記數組
int[] check = new int[n];
//需要廣播的服務器的數量
int ans = 0;
Stack<Integer> stack = new Stack<>();
// 遍歷每個服務器
for (int i = 0; i < n; i++) {
// 如果服務器 i 沒有被訪問過，就以它為起點進行 DFS
if (check[i] == 0) {
ans++; // 新的連通分量，計數器加 1
stack.add(i); // 將當前服務器加入棧
check[i] = 1; // 標記為已訪問
// 開始 DFS
while (!stack.isEmpty()) {
// 彈出當前服務器
int cur = stack.pop();
// 遍歷所有服務器，找到與 cur 相連且未訪問的服務器
for (int j = 0; j < n; j++) {
if (j != cur && matrix[cur][j] == 1 && check[j] == 0) {
// 將未訪問的服務器加入棧
stack.push(j);
// 將未訪問的服務器加入棧
check[j] = 1;
}
}
}
}
}
System.out.println(ans);
}
}總結
DFS 是一種非常重要的圖遍歷算法，適用于許多場景。遞歸實現簡單直觀，但可能會受到棧深度的限制；迭代實現則避免了這個問題，但代碼稍復雜一些。根據具體需求選擇合適的實現方式。
責任編輯：武曉燕
來源：
修己xj
