本章内容

• 学习使用新的数据结构图来建立网络模型。
• 学习广度优先搜索，你可对图使用这种算法回答诸如“到X的最短路径是什么”等问题。
• 学习有向图和无向图。
• 学习拓扑排序，这种排序算法指出了节点之间的依赖关系。

本章将介绍图。首先，我将说说什么是图（它们不涉及X轴和Y轴），再介绍第一种图算法——广度优先搜索（breadth-first search， BFS）。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

• 编写国际跳棋AI，计算最少走多少步就可获胜；
• 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
• 根据你的人际关系网络找到关系最近的医生。

在我所知道的算法中，图算法应该是最有用的。请务必仔细阅读接下来的几章，这些算法你将经常用到。