算法系列之搜索算法-深度优先搜索DFS

简介: 深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。

8483ff80-2b40-43e3-b83f-139a7ee7b337.jpg

随着每年"金三银四"招聘季的到来,许多求职者开始积极备战面试。在众多面试环节中,机试往往是不可或缺的一环,而算法能力更是机试考核的重点。为此,我们特别推出算法系列文章,帮助大家系统复习算法知识。今天,我们将首先探讨搜索算法中的重要内容——深度度优先搜索(DFS)。

图的介绍

图(Graph)是一种非线性的数据结构,由顶点(Vertex)和边(Edge)组成。如下图所示

_20250219193211.jpg
分类如下:

  • 无向图(Undirected Graph):边没有方向,表示双向关系。

  • 有向图(Directed Graph):边有方向,表示单向关系。

  • 加权图(Weighted Graph):边带有权重。

  • 无权图(Unweighted Graph):边没有权重。

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

深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。

DFS 可以借助于栈或者来实现。栈具有”后进先出(LIFO)”特性,可以是有栈或者递归来实现遍历。其实现步骤如下:

  1. 访问节点:从起始节点开始,访问当前节点。

  2. 递归

  • 递归访问邻居:对于当前节点的每一个未访问过的邻居节点,递归地调用 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 是一种非常重要的图遍历算法,适用于许多场景。递归实现简单直观,但可能会受到栈深度的限制;迭代实现则避免了这个问题,但代码稍复杂一些。根据具体需求选择合适的实现方式。

目录
相关文章
|
19天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
21天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
320 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
22天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
|
22天前
|
存储 算法 数据可视化
基于禁忌搜索算法的TSP问题最优路径搜索matlab仿真
本程序基于禁忌搜索算法解决旅行商问题(TSP),旨在寻找访问多个城市的最短路径。使用 MATLAB 2022A 编写,包含城市坐标生成、路径优化及结果可视化功能。通过禁忌列表、禁忌长度与藐视准则等机制,提升搜索效率与解的质量,适用于物流配送、路径规划等场景。
|
2月前
|
机器学习/深度学习 并行计算 算法
MATLAB实现利用禁忌搜索算法解决基站选址问题
MATLAB实现利用禁忌搜索算法解决基站选址问题
76 0
|
3月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
138 0
|
14天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
16天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
103 1
|
15天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)

热门文章

最新文章