深度优先（DFS）和广度优先（BFS）
2024-09-01 02:34:47
深度优先（Depth-First-Search）和广度优先（Breadth-First-Search）是我们遍历图的两种方式，它们都属于穷举法，用来系统的遍历图中的所有顶点
关于如何再一个有向图/无向图中进行深度优先或者是广度优先，大家应该都清楚了
但为了真正认识到该算法的功效和深度，我们不应该根据图的图形，而是应该根据它的邻接矩阵或者邻接链表来跟踪算法的操作
可以用一张表来比较两者
| 项目 | DFS | BFS |
| 数据结构 | 栈 | 队列 |
| 顶点顺序的种类 | 两种顺序 | 一种顺序 |
| 变得种类（无向图） | 树向边和回边 | 数向边和交叉边 |
| 应用 | 连通性，无环性，关节点 | 无环性，连通性，最少边路径 |
| 邻接矩阵的效率 | V^2 | V^2 |
| 邻接链表的效率 | V+E | V+E |
注：V为图中顶点数量，E是边的数量
本文参考《introduction to the design and analysis of algorithms》
最新文章
- kubernetes多节点部署解析
- 常用SQLPLUS工具命令
- Know How To Use ID_NULL Function To Search An Object In Oracle Forms
- linux 常用命令；
- 【Andorid开发框架学习】之Mina开发之客户端开发
- Node.js异常处理
- Git客户端图文详解如何安装配置GitHub操作流程攻略
- 【UI控件总结】【UIScrollView】深入理解篇UIScrollerView
- 【WEB小工具】EncodingFilter—设置全局编码
- 《第一行代码》学习笔记36－服务Service（3）
- [置顶] IT屌丝的离职申请
- telnet模拟http訪问
- c++中string的用法
- 美团点评DBProxy读写分离使用说明
- 【Shell脚本学习指南笔记】重定向文件描述符 2>&1
- 【BZOJ1076】奖励关（动态规划，数学期望）
- redis客户端可以连接集群，但JedisCluster连接redis集群一直报Could not get a resource from the pool
- python学习day21 面向对象(三)嵌套/特殊方法
- 第六章· Redis高可用sentinel
- swig模板引擎汇总