读《图解算法》05-广度优先搜索

发表于

广度优先算法简单介绍

breadth-first search ，以下简称 BFS

  • 能让你找出两样东西之间的最短距离，不过最短距离的含义有很多。

可以干什么（感受一下多强大）

  • 编写国际跳棋 AI，计算最少走多少就可以获胜
  • 根据人际关系网络找到关系最近的医生

可以回答两类问题

  • 从节点 A 出发，有前往节点 B 的途径吗
  • 从节点 a 出发，前往节点 b 的路径哪条最短

如何实现

  • 创建一个队列，存储要检查的人
  • 从队列弹出一个人，检查这个人是否是想要的，不是的话，把这个人的邻居加入队列
  • 假设队列里面肯定有重复的，所以要将检查的人标记，不能检查两次，不然会出现无限循环的情况
  • 可以专门存一个数组来记录检查过的人，或者用散列表存储，本质去掉重复

运行时间

  • 在整个人际关系网找到正确的，意味着要沿每条边前行，因此运行时间为 O(n)
  • 还使用了队列，其中要包含每个检查的人。将一个人添加到队列是 O（1），n 个人就是 O（n）
  • 所以运行时间通常为 O(V+E)，v 为定点数，e 为边数

图

简介

想象以下场景

  • 从我家到公园，需要几步，求最短路径
  • 一个欠钱的关系图，几个人之间的

组成

  • 图是由节点和边组成。
  • 图用于模拟不同的东西是如何相连的

有向图和无向图

  • 有向图的关系是单向的，从节点 a 到节点 b，但不能反过来
  • 无向图直接相连

查找算法

  • 有序列表的查找算法有二分法，同样，图的查找算法是广度优先搜索

如何实现图

  • 因为图是由多个节点组成，每个节点都与邻近节点相连，怎么表示我->bob 这样的关系，可以使用散列表，将 key 映射到 value
  • 这里我们将节点映射到所有邻居
  • 图不过是一系列的节点和边的组合
1
2
3
4
5
let graph = {};
graph["me"] = ["alice", "bob"];
graph["bob"] = ["peggy"];
graph["alice"] = ["peggy"];
graph["peggy"] = [];

队列

和生活中的队列完全一样

  • 是一个先进先出的数据结构
  • 队列只支持两种操作：入队和出队

树

特殊的图，没有往后指的边，自上而下

  • 假设正在规划一场婚礼，并有一个很大的图
  • 其中充满着需要做的事，但是却不知道从何开始
  • 可以使用拓扑排序来创建一个有序列表