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

数据结构与算法之深度优先算法详解

深度优先算法(Depth First Search,DFS)是一种常见的图形算法,它是一种用于遍历或搜索树或图的算法。在深度优先搜索中,我们首先探索一个子树的深度,然后再回溯到父节点,接着探索另一个子树的深度,直至搜索结束。

深度优先算法的基本思想是沿着树的深度遍历树的节点。深度优先算法的工作原理类似于树的前序遍历,即首先访问根节点,然后依次访问该节点的子节点。

深度优先算法可以用递归实现,也可以使用栈来实现。下面我们详细介绍这两种实现方式。

  1. 递归实现深度优先算法

下面是使用递归实现深度优先算法的示例代码:

void dfs(int node, vector &visited, vector> &graph) {// 标记节点node已被访问visited[node] = true;// 访问节点nodecout << node << " ";// 遍历node的所有邻居节点for (int i = 0; i < graph[node].size(); i++) {int neighbor = graph[node][i];// 如果邻居节点未被访问,则递归访问它if (!visited[neighbor]) {dfs(neighbor, visited, graph);}}
}

在这个示例中,我们首先定义一个函数dfs,它接收三个参数,分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部,我们首先将当前节点标记为已访问,并输出该节点的编号。然后我们遍历该节点的所有邻居节点,如果邻居节点未被访问,则递归地访问它。递归的终止条件是遍历完所有节点。

  1. 栈实现深度优先算法

下面是使用栈实现深度优先算法的示例代码:

void dfs(int node, vector &visited, vector> &graph) {stack stk;// 将起始节点入栈stk.push(node);while (!stk.empty()) {// 取出栈顶元素int cur = stk.top();stk.pop();// 如果当前节点未被访问,则访问它if (!visited[cur]) {visited[cur] = true;cout << cur << " ";// 将当前节点的邻居节点入栈for (int i = graph[cur].size() - 1; i >= 0; i--) {int neighbor = graph[cur][i];if (!visited[neighbor]) {stk.push(neighbor);}}}}
}

在这个示例中,我们首先定义一个函数dfs,它接收三个参数,分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部,我们创建一个栈,并将初始节点node入栈。在栈未空之前,我们重复执行以下步骤:

  • 取出栈顶元素
  • 如果当前节点未被访问,则将其标记为已访问,并输出该节点的编号
  • 遍历该节点的所有邻居节点,如果邻居节点未被访问,则将其入栈

在程序的最后,我们完成了整个深度优先遍历。

深度优先算法的时间复杂度为$O(V+E)$,其中$V$是图的节点数量,$E$是图的边数量。因为在遍历每个节点和边的时候,每个节点和边都会被访问一次。另外,深度优先算法的空间复杂度为$O(V)$,其中$V$是图的节点数量,因为需要存储每个节点的访问状态。

http://www.lryc.cn/news/68686.html

相关文章:

  • C# 给winfrom窗体添加皮肤控件
  • 数据分析真的很火吗?真的有很多企业需要这样的岗位吗?求大佬指点。
  • 100 个 Go 错误以及如何避免:9~12
  • 用户/用户组管理
  • 如何进行TCP抓包调试?
  • 分享一个国内可用的ChatGPT网站,免费无限制,支持AI绘画 - AI 百晓生
  • API安全性的要素与开发人员必修课测试
  • leetcode 651. 4键键盘
  • Python垃圾回收机制
  • Grafana插件安装并接入zabbix数据源(03)
  • 简述 JavaScript 中 prototype
  • 一觉醒来Chat gpt就被淘汰了
  • 13款JavaScript图像处理库,建议收藏备用
  • uniapp m3u8格式视频加载
  • iOS描述文件(.mobileprovision)一键申请
  • 进行性能压力测试的原因、目的和好处
  • 【计算机视觉】如何利用 CLIP 做简单的人脸任务?(含源代码)
  • 基于显扬科技3D视觉相机的医疗试管分拣系统
  • 编译zlib
  • 如何让“ChatGPT自己写出好的Prompt的“脚本在这里
  • 菜单选择shell
  • Redis高可用性详解
  • MySQL(1) ---- 数据库介绍与MySQL概述
  • 面试题之软件测试流程
  • MyBatis中#{}与${}的区别,与各自的应用场景
  • 泛型类相关
  • 一文速学数模-季节性时序预测SARIMA模型详解+Python实现
  • 二叉树与图(C++刷题笔记)
  • STM32-ADC多通道输入实验
  • javaIO流之文件流