当前位置： 首页 > news >正文

DFS（深度优先搜索）

news 2025/6/8 9:53:53

简介：

DFS（Depth-First Search，深度优先搜索）是一种经典的图遍历算法，广泛应用于树结构遍历、图论问题（如连通性分析、拓扑排序）、路径搜索、回溯算法等领域。以下是其发展历程的详细梳理：

一、起源与早期理论基础（1950 年代–1960 年代）

1. 理论雏形：树结构的遍历
  • 背景：早期计算机科学中，树结构（如二叉树）的遍历是基础问题。深度优先搜索的思想最初用于树的遍历（如先序、中序、后序遍历），其核心是 “尽可能深入分支，回溯时处理未访问节点”。
  • 关键人物：1950 年代，计算机科学家在研究编译器设计、符号处理时，自然应用了类似 DFS 的递归遍历方法（如解析表达式树）。
2. 图论中的正式提出
  • 1959 年：美国数学家爱德华・F・摩尔（Edward F. Moore）在研究迷宫问题时，提出了一种 “尽可能深入探索，遇死胡同则回溯” 的搜索策略，这被视为 DFS 在图论中的早期应用。他的算法用于寻找迷宫中的最短路径，虽未明确命名为 DFS，但奠定了其核心思想。
  • 1960 年代：随着图论与计算机科学的结合，DFS 作为一种系统化的图遍历算法被正式定义。其与广度优先搜索（BFS）的对比成为图算法的基础内容。

二、算法成熟与计算机科学中的应用（1970 年代–1980 年代）

1. 算法复杂度分析与标准化
  • 1973 年：计算机科学家罗伯特・塔扬（Robert Tarjan）在图论算法领域取得突破性进展。他利用 DFS 开发了一系列线性时间算法，如：
    • 强连通分量检测：Tarjan 算法通过 DFS 遍历图，在线性时间内找出有向图的强连通分量。
    • 双连通分量检测：用于无向图的关节点（割点）和桥的检测。
  • 意义：Tarjan 的工作将 DFS 从简单的遍历方法提升为解决复杂图论问题的核心工具，并确立了其在算法分析中的重要地位（时间复杂度为 O (V+E)，V 为顶点数，E 为边数）。
2. 回溯算法与 DFS 的结合
  • 1970 年代：回溯算法（Backtracking）作为一种系统搜索解空间的方法，与 DFS 深度结合。典型应用包括：
    • 八皇后问题：通过 DFS 遍历棋盘状态空间，递归尝试放置皇后并回溯冲突情况。
    • 迷宫求解：利用 DFS 探索所有可能路径，记录路径并在死胡同时回溯。
  • 特点：回溯算法本质是带剪枝的 DFS，通过递归实现状态转移，成为解决组合优化问题的经典方法。

三、数据结构与实现方式的演进（1990 年代–2000 年代）

1. 从递归到迭代：实现方式的优化
  • 早期：DFS 通常通过递归实现，简洁但受限于系统栈深度（可能导致栈溢出，如处理大规模图时）。
  • 改进：1990 年代后，迭代实现（显式使用栈结构）逐渐普及，避免了递归深度限制，更适合处理大规模数据。
2. 与数据结构的结合
  • 邻接表与邻接矩阵：DFS 的效率依赖图的存储方式。邻接表（链表结构）更适合稀疏图，时间复杂度更优；邻接矩阵（二维数组）适合稠密图，但空间复杂度较高。
  • 哈希表与集合：在记录已访问节点时，哈希表（如 Python 的 set）的平均查询时间为 O (1)，提升了算法效率。

四、扩展应用与现代发展（2010 年代至今）

1. 在复杂系统中的应用
  • 计算机游戏：路径寻找（如 A * 算法结合 DFS 预处理）、地图生成（如利用 DFS 生成随机迷宫）。
  • 编译器设计：语法树遍历、符号表构建。
  • 网络爬虫：早期爬虫通过 DFS 遍历网页链接，但因可能陷入深层页面导致效率问题，逐渐被 BFS（优先抓取浅层页面）取代。
2. 与其他算法的融合
  • 记忆化搜索（Memoization）：在动态规划问题中，DFS 结合缓存（记忆化）优化重复计算，如斐波那契数列的递归实现。
  • 启发式搜索：在 DFS 基础上引入启发式函数（如深度限制、迭代加深），形成迭代加深深度优先搜索（IDDFS），用于平衡深度与广度，避免无限递归。
3. 大数据与并行计算中的挑战
  • 局限性：传统 DFS 为串行算法，处理大规模图（如社交网络、知识图谱）时效率不足。
  • 改进方向：
    • 并行 DFS：利用多线程或分布式计算（如 MapReduce）加速遍历，但需解决线程安全、负载均衡等问题。
    • 近似算法：在允许误差的场景下，使用随机化策略（如随机 DFS）降低时间复杂度。

五、经典变体与衍生算法

  1. 深度限制搜索（Depth-Limited Search, DLS）

    • 设定搜索深度上限，避免陷入无限递归，用于处理树深度未知的问题。

  2. 迭代加深深度优先搜索（Iterative Deepening DFS, IDDFS）

    • 结合 BFS 的层次扩展思想，逐层增加深度限制进行 DFS，兼具 DFS 的空间效率与 BFS 的最短路径特性，适用于未知深度的树搜索。

  3. 回溯算法（Backtracking）

    • 本质为带剪枝的 DFS，用于求解组合问题（如子集和、排列生成），通过提前排除无效路径减少计算量。

  4. 强连通分量算法（Tarjan 算法、Kosaraju 算法）

    • 基于 DFS 的图论算法，用于分析有向图的连通性，在网络分析、流程建模中广泛应用。

基本框架：

int dfs(int k)
{if (到目的地){对结果进行处理;return;}for(i=1;i<=运算符种数;i++){if(满足条件){标记保存结果;dfs(k+1);恢复：保存结果之前的状态{回溯一步}}}
}

代码：

c++:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 递归实现DFS（推荐）
void dfsRecursive(int node, vector<bool>& visited, const vector<vector<int>>& adj) {visited[node] = true;cout << "访问节点: " << node << endl;// 遍历所有邻接节点for (int neighbor : adj[node]) {if (!visited[neighbor]) {dfsRecursive(neighbor, visited, adj);}}
}// 迭代实现DFS（使用栈）
void dfsIterative(int start, const vector<vector<int>>& adj) {int n = adj.size();vector<bool> visited(n, false);stack<int> stack;stack.push(start);while (!stack.empty()) {int node = stack.top();stack.pop();if (!visited[node]) {visited[node] = true;cout << "访问节点: " << node << endl;// 注意：栈是后进先出，所以逆序压入邻接节点for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {if (!visited[*it]) {stack.push(*it);}}}}
}int main() {// 示例：构建一个简单的图（邻接表表示）int n = 5; // 节点数vector<vector<int>> adj(n);// 添加边（无向图）adj[0].push_back(1);adj[0].push_back(2);adj[1].push_back(3);adj[2].push_back(4);cout << "递归DFS遍历结果:" << endl;vector<bool> visited(n, false);dfsRecursive(0, visited, adj);cout << "\n迭代DFS遍历结果:" << endl;dfsIterative(0, adj);return 0;
}

Python：

# 递归实现DFS（推荐）
def dfs_recursive(node, visited, adj):visited[node] = Trueprint(f"访问节点: {node}")# 遍历所有邻接节点for neighbor in adj[node]:if not visited[neighbor]:dfs_recursive(neighbor, visited, adj)# 迭代实现DFS（使用栈）
def dfs_iterative(start, adj):visited = [False] * len(adj)stack = [start]while stack:node = stack.pop()if not visited[node]:visited[node] = Trueprint(f"访问节点: {node}")# 逆序压入邻接节点（保持与递归版本相同的遍历顺序）for neighbor in reversed(adj[node]):if not visited[neighbor]:stack.append(neighbor)# 示例：构建一个简单的图（邻接表表示）
if __name__ == "__main__":# 节点数n = 5# 邻接表adj = [[] for _ in range(n)]# 添加边（无向图）adj[0].append(1)adj[0].append(2)adj[1].append(3)adj[2].append(4)print("递归DFS遍历结果:")visited = [False] * ndfs_recursive(0, visited, adj)print("\n迭代DFS遍历结果:")dfs_iterative(0, adj)

两种实现方式的说明：

  1. 递归实现：

    • 简洁直观，适合快速实现
    • 利用系统调用栈，隐式维护访问路径
    • 注意：当图的深度很大时可能导致栈溢出

  2. 迭代实现：

    • 使用显式栈结构替代递归调用
    • 避免栈溢出问题，适合大规模图
    • 需要手动管理节点的访问顺序（注意压栈顺序与递归的一致性）
希望这些代码能帮助您理解并解决这个问题，如果有问题，请随时提问。
  蒟蒻文章，神犇勿喷，点个赞再走吧！QAQ
http://www.xdnf.cn/news/926641.html

相关文章：

  • 从游戏到自动驾驶：互联网时代强化学习如何让机器学会自主决策？
  • 基于STM32的DHT11温湿度远程监测LCD1602显示Proteus仿真+程序+设计报告+讲解视频
  • Global Security Markets 第 10 章衍生品知识点总结​
  • 第一章 计算机系统构成及硬件基础知识
  • 【2025】typora 安装及破解
  • ＜ 自用文 OS有关 新的JD云主机＞ 国内 京东云主机 2C4G 60G 5Mb 498/36月 Ubuntu22
  • XGBoost时间序列预测之-未来销量的预测
  • 跳跃游戏 dp还是线段树优化
  • 论文调研_BCSD综述论文调研
  • IOS性能优化
  • Shell 命令及运行原理 + 权限的概念（7）
  • SpringBoot 框架实现文件上传下载分享
  • 泛型接口：允许在接口中使用类型参数
  • gis 高程影像切片地图发布geoserver
  • 深圳SMT贴片工艺优化关键步骤
  • 财务后台系统
  • Python Day44 学习（日志Day12复习）
  • 嵌入式部分BSP相关实现
  • LeetCode 每日一题 2025/6/2-2025/6/8
  • 从golang的sync.pool到linux的slab分配器
  • Android开发 系统签名jks制作和问题汇总
  • 实现简易动效
  • 杭州瑞盟 MS35774/MS35774A 低噪声256细分微步进电机驱动，用于空调风门电机驱动，香薰电机驱动
  • ViiTor实时翻译 2.4.2 | 完全免费的同声传译软件 实测识别率非常高 可以识别视频生成字幕
  • 看看不同主干的参数量是多少
  • 【Linux】SSH：免密登录
  • Egg.js框架的基本介绍与用法，以及如何连接数据库并对数据库进行增删改查
  • Go 语言中的 make 函数详解
  • AI推理服务的高可用架构设计
  • 第9篇：数据库中间件的容错机制与高可用架构设计