06-重温广度优先搜索

重温广度优先搜索

在无权图中，查找最短路径意味着要找到起始顶点和目标顶点之间边最少的路径。若要构建超级高铁网络，或许首先连接相距最远而人口密集的海滨城市会很有意义。这就提出了一个问题：“Boston和Miami之间的最短路径是什么？”

提示 　本节假定你已阅读过第2章。在继续阅读之前，请确保你已熟悉第2章中有关广度优先搜索的内容。

幸好我们已经有了一个查找最短路径的算法，求解本章问题时拿来复用即可。第2章中介绍的求解迷宫问题的广度优先搜索算法对图也同样适用。事实上，第2章中处理的迷宫其实就是图。顶点就是迷宫中的位置，边则是可以由一个位置移动到另一个位置的路线。在无权图中，广度优先搜索将会找到任意两个顶点之间的最短路径。

第2章中的广度优先搜索代码可以拿来复用，以处理 Graph 。事实上，不用做任何改动即可复用。这正是编写通用代码的威力！

回想一下，第2章中的 bfs() 需要3个参数：初始状态、用于测试目标状态的 Callable （类似于读函数的对象）、用于查找给定状态的后续状态的 Callable 。初始状态将是由字符串“Boston”表示的顶点。目标测试对象将是检查顶点是否等于“Miami”的lambda表达式。最后可以用 Graph 的 neighbors_for_vertex() 方法生成后续顶点。

考虑到超级高铁计划的特点，我们可以在graph.py主体部分的末尾添加一些代码，以实现在 city_graph 上找到Boston和Miami之间的最短路径。具体代码如代码清单4-5所示。

注意 　在代码清单4-5中， bfs 、 Node 和 node_to_path 是从 Chapter2 包的 generic_search 模块导入的。为此，graph.py的上一级目录将被添加到Python的搜索路径（ '..' ）中。因为本书代码库的结构是把每章都放入了各自的目录中，所以才需要如此，此时的目录结构大致是Book->Chapter2->generic_search.py和Book-> Chapter4-> graph.py。如果你的目录结构明显不是如此，则需要找到一种方法把generic_search.py添加到路径中，并且可能需要修改一下 import 语句。实在不行的话，只需将generic_search.py复制到包含graph.py的同一目录下即可，并把 import 语句修改为 from generic_search import bfs, Node, node_to_path 。

代码清单4-5　graph.py（续）

# Reuse BFS from chapter 2 on city_graph
import sys
sys.path.insert(0, '..') # so we can access the Chapter2 package in the parent directory
from Chapter2.generic_search import bfs, Node, node_to_path
bfs_result: Optional[Node[V]] = bfs("Boston", lambda x: x == "Miami",
    city_graph.neighbors_for_vertex)
if bfs_result is None:
    print("No solution found using breadth-first search!")
else:
    path: List[V] = node_to_path(bfs_result)
    print("Path from Boston to Miami:")
    print(path)

输出结果应该如下所示：

Path from Boston to Miami:
['Boston', 'Detroit', 'Washington', 'Miami']

这里考虑的是边的数量，从Boston到Detroit，然后到Washington，再到Miami，由这3条边构成了最短路径。图4-4高亮显示了这条路径。