《图解算法》第6章 广度优先搜索

第6章 广度优先搜索

广度优先搜索让你能够找出两样东西之间的最短距离

1. 编写国际象棋AI，计算最少走多少步就可获胜
2. 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词
3. 根据你的人际关系网络找到关系最近的医生

图简介

你经常要找出最短路径，这可能是前往朋友家的最短路径。解决最短路径问题的算法被称为广度优先搜索

• 需要两个步骤

1. 使用图来建立问题模型
2. 使用广度优先搜索解决问题

图是什么

• 图由节点（node）和边（edge）组成

• 一个节点可能与众多节点直接相连，这些节点被称为邻居

广度优先搜索

• 广度优先搜索是一种用于图的查找算法，可帮助回答两类问题

1. 从节点A出发，有前往节点B的路径吗？
2. 从节点A出发，前往节点B的哪条路径最短？

查找最短路径

• 一度关系在二度关系之前加入查找名单。先在一度关系中查找，再在二度关系中查找

队列

• 队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作

1. 入队
2. 出队

队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构

实现图

• 图由多个节点组成。每个节点都与邻近节点相连，如果表示类似于“你--》Bob”这样的关系呢？好在你知道的一种结构让你能够表示这种关系，它就是散列表！
• 散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居