随着每年"金三银四"招聘季的到来，许多求职者开始积极备战面试。在众多面试环节中，机试往往是不可或缺的一环，而算法能力更是机试考核的重点。为此，我们特别推出算法系列文章，帮助大家系统复习算法知识。今天，我们将首先探讨搜索算法中的重要内容——深度度优先搜索（DFS）。
图的介绍
图(Graph)是一种非线性的数据结构，由顶点（Vertex）和边（Edge）组成。如下图所示
分类如下：
-
无向图（Undirected Graph）：边没有方向，表示双向关系。
-
有向图（Directed Graph）：边有方向，表示单向关系。
-
加权图（Weighted Graph）：边带有权重。
-
无权图（Unweighted Graph）：边没有权重。
深度优先搜索（DFS, Depth-First Search）
深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索，直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索，直到不能够在继续为止，然后在折返，开始搜索下一条候补路径。
DFS 可以借助于栈或者来实现。栈具有”后进先出（LIFO）”特性，可以是有栈或者递归来实现遍历。其实现步骤如下：
-
访问节点：从起始节点开始，访问当前节点。
-
递归
-
递归访问邻居：对于当前节点的每一个未访问过的邻居节点，递归地调用 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 没有被访问过，就以它为起点进行 DFSif (check[i] == 0) {ans++; // 新的连通分量，计数器加 1stack.add(i); // 将当前服务器加入栈check[i] = 1; // 标记为已访问// 开始 DFSwhile (!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 是一种非常重要的图遍历算法，适用于许多场景。递归实现简单直观，但可能会受到栈深度的限制；迭代实现则避免了这个问题，但代码稍复杂一些。根据具体需求选择合适的实现方式。