算法系列之搜索算法-深度优先搜索DFS
随着每年"金三银四"招聘季的到来，许多求职者开始积极备战面试。在众多面试环节中，机试往往是不可或缺的一环，而算法能力更是机试考核的重点。为此，我们特别推出算法系列文章，帮助大家系统复习算法知识。今天，我们将首先探讨搜索算法中的重要内容——深度度优先搜索（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 stack = new Stack(); // 使用HashSet记录已访问的节点 Set 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 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 = newNode(1); Node node2 = newNode(2); Node node3 = newNode(3); Node node4 = newNode(4); Node node5 = newNode(5); Node node6 = newNode(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); }}
[*]1.
[*]2.
[*]3.
[*]4.
[*]5.
[*]6.
[*]7.
[*]8.
[*]9.
[*]10.
[*]11.
[*]12.
[*]13.
[*]14.
[*]15.
[*]16.
[*]17.
[*]18.
[*]19.
[*]20.
[*]21.
[*]22.
[*]23.
[*]24.
[*]25.
[*]26.
[*]27.
[*]28.
[*]29.
[*]30.
[*]31.
[*]32.
[*]33.
[*]34.
[*]35.
[*]36.
[*]37.
[*]38.
[*]39.
[*]40.
[*]41.
[*]42.
[*]43.
[*]44.
[*]45.
[*]46.
[*]47.
[*]48.
[*]49.
[*]50.
[*]51.
[*]52.
[*]53.
[*]54.
[*]55.
[*]56.
[*]57.
[*]58.
[*]59.
[*]60.
[*]61.
[*]62.
[*]63.
[*]64.
[*]65.
[*]66.
[*]67.
[*]68.
[*]69.
[*]70.
[*]71.
[*]72.
[*]73.
[*]74.
[*]75.
[*]76.
[*]77.
[*]78.
[*]79.
[*]80.
[*]81.
[*]82.
[*]83.
[*]84.
[*]85.
[*]86.
[*]87.
[*]88.
[*]89.
[*]90.
[*]91.
[*]92.
[*]93.
[*]94.
[*]95.
[*]96.
[*]97.
[*]98.
[*]99.
[*]100.
[*]101.
[*]102.
[*]103.
[*]104.
[*]105.
[*]106.
[*]107.
DFS的特点
[*]时间复杂度：O(V+E)
[*]空间复杂度：O(V)
[*]适用场景：连通性检测、路径查找、迷宫求解
DFS 示例题
以下列举了一些机试题
广播服务器
题目描述：给定一个大小为 N×N 的二维矩阵 matrix，表示 N 个服务器之间的连接情况。matrix = 1 表示服务器i 和 j 直接连接，matrix = 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; for (int i = 0; i < n; i++) { String[] line = i==0 ? firstLine:scanner.nextLine().split(" "); for (int j = 0; j < n; j++) { matrix = Integer.parseInt(line); } } //初始化标记数组 int[] check = new int; //需要广播的服务器的数量 int ans = 0; Stack stack = new Stack(); // 遍历每个服务器 for (int i = 0; i < n; i++) { // 如果服务器 i 没有被访问过，就以它为起点进行 DFS if (check == 0) { ans++; // 新的连通分量，计数器加 1 stack.add(i); // 将当前服务器加入栈 check = 1; // 标记为已访问 // 开始 DFS while (!stack.isEmpty()) { // 弹出当前服务器 int cur = stack.pop(); // 遍历所有服务器，找到与 cur 相连且未访问的服务器 for (int j = 0; j < n; j++) { if (j != cur && matrix == 1 && check == 0) { // 将未访问的服务器加入栈 stack.push(j); // 将未访问的服务器加入栈 check = 1; } } } } } System.out.println(ans); }}
[*]1.
[*]2.
[*]3.
[*]4.
[*]5.
[*]6.
[*]7.
[*]8.
[*]9.
[*]10.
[*]11.
[*]12.
[*]13.
[*]14.
[*]15.
[*]16.
[*]17.
[*]18.
[*]19.
[*]20.
[*]21.
[*]22.
[*]23.
[*]24.
[*]25.
[*]26.
[*]27.
[*]28.
[*]29.
[*]30.
[*]31.
[*]32.
[*]33.
[*]34.
[*]35.
[*]36.
[*]37.
[*]38.
[*]39.
[*]40.
[*]41.
[*]42.
[*]43.
[*]44.
[*]45.
[*]46.
[*]47.
[*]48.
总结
DFS 是一种非常重要的图遍历算法，适用于许多场景。递归实现简单直观，但可能会受到栈深度的限制；迭代实现则避免了这个问题，但代码稍复杂一些。根据具体需求选择合适的实现方式。
页:
[1]