76 第6章 广度优先搜索
第6章
广度优先搜索
本章内容
学习使用新的数据结构图来建立网络模型。
学习广度优先搜索,你可对图使用这种算法回答诸如“到X的最短路径是什么”等问题。
学习有向图和无向图。
学习拓扑排序,这种排序算法指出了节点之间的依赖关系。
本章将介绍图。首先,我将说说什么是图(它们不涉及X轴和Y轴),再介绍第一种图算法——
广度优先搜索(breadth-first search,BFS)。
广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!使用广
度优先搜索可以:
编写国际跳棋AI,计算最少走多少步就可获胜;
编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将
READED改为READER需要编辑一个地方;
根据你的人际关系网络找到关系最近的医生。
在我所知道的算法中,图算法应该是最有用的。请务必仔细阅读接下来的几章,这些算法你
将经常用到。
6.1 图简 ...
附件列表