算法图解 - 广度优先搜索
🏷️ 《算法图解》
最短路径问题 (shortest-path problem)
- 解决最短路径问题的算法被称为广度优先搜索
图
图模拟一组连接
图由 节点 (node) 和 边 (edge) 组成
一个节点可能于众多节点直接连接,这些节点被称为 邻居
分为有向图 (directed graph) 和无向图 (undirected graph)
广度优先搜索
广度优先搜索是一种用于图的查找算法,可帮助回答两类问题
从节点 A 出发,有前往节点 B 的路径吗?
从节点 A 出发,前往节点 B 的哪条路径最短?
队列
只有两种操作
入队
出队
是一种先进先出 (First In First Out, FIFO) 的数据结构
实现图
使用散列表表示图的关系
散列表的 key 表示节点
散列表的 value 表示该节点的边
实现算法
创建一个队列,存储所有的 key,
判断队列是否为空
为空,则处理结束
不为空,则处理继续
从队列中弹出一个元素
判断是否检查过该元素
已检查过,则跳转到处理 2 继续执行
未检查过,则处理继续
判断该元素符不符合要求
符合,则处理结束
不符合则跳转到处理 2 继续执行
运行时间
,通常写作其中 V 为顶点 (vertice) 数,E 为边数