[测试] 广度优先搜索实现的笔记

引言

本文来自 Amit Patel 关于广度优先搜索算法实现的博客，请先阅读文中超链接给出的代码示范（这里给出的均为原博客链接）再阅读本文。

来源：Red Blob Games
翻译：Eldath
审校：craft

我曾在我这篇塔防游戏寻路算法的说明页整理过一些有关广度优先搜索实现的笔记。然而它们都已过时了。

大家可以查看这个替代版的代码，同时包含 Python 和 C++ 的实现版本。

内部访问标记

在那篇文章中，我们通过外部访问标记使用数组或者哈希表来存储节点的访问标记 visited 以及 distance（距离）和 came_from（来源）等数据。使用内部访问标记是一种替代的可行之策，这时数据会保存在节点的数据结构之中。

那么这两种策略孰优孰劣呢？尽管内部访问标记会稍微快一点（避免了哈希表遍历）但外部访问标记的方式却更加整洁，因为你可以在无需修改图的数据结构的情况下进行搜索。它还支持多个同时进行的搜索，无论是通过多线程的方式还是借助协程。这里给出一个使用内部访问标记的实例节点类：

class Node:
    def __init__(self, name):
        self.visited = False
        self.name = name
        slef._neighbors = []

    def neighbors(slef):
        return self._neighbors

以及这里是一个示例的图：

A = Node("A")
B = Node("B")
C = Node("C")
D = Node("D")
E = Node("E")
A._neighbors = [B]
B._neighbors = [A, C]
C._neighbors = [D]
D._neighbors = [E]
E._neighbors = []
start = A

如果我们使用内部访问标记，为了再次运行该算法，我们必须重置 visited 为False。因此，在运行算法之前我们必须这样做：

ALL_NODES = [A, B, C, D, E]
      
frontier = Queue()
frontier.put(start)
for node in ALL_NODES:
    node.visited = False
start.visited = True

while not frontier.empty():
    current = frontier.get()
    callback(current)
    for next in current.neighbors():
        if not next.visited:
            next.visited = True
            frontier.put(next)

下载例程。

或者，我们可以通过保存所有访问过节点的列表，来在运行算法后进行复位：

frontier = Queue()
frontier.put(start)
start.visited = True
visited_nodes = [start]

while not frontier.empty():
    current = frontier.get()
    for next in current.neighbors():
        if not next.visited:
            next.visited = True
            visited_nodes.append(next)
            frontier.put(next)

for node in visited_nodes:
    node.visited = False

下载例程。

该选择哪一个呢？具体到本例其实无关紧要，因为在这里我们会访问所有的节点。但如果你最终将访问所有的节点，第一种实现会稍微快一些；然而，如果你需要在访问完所有节点前退出，那么第二种方法会更快。第一种实现每次都会遍历所有节点，而第二种方式只访问那些我们已经访问过的节点。

节点编号

（提醒：多数人无需进行这种优化）为了使操作哈希表的方法能够工作，节点需要以哈希表的形式存储。另一种实现是为每个节点指定一个整型ID，这样您可以使用一个位数组（bit array）来存储是否已访问过该节点的信息，并且使一个矩形整型数组来储存 distance 和 came_from 等信息。

对于 C 或 C++ 的使用者来说，无须关心存储 distance和 came_from 数据的数组的初始化（潜在的大胜利！）。你只需要初始化位数组（bit array）,它会将 64 个 ID 压缩进一个长整型（long）变量之中，且仅当这个数组中的对应元素为 True 时,存储 distance 和 came_from 的数组才会被初始化。

如果堆栈空间足够，你可以考虑将这两个数组放入栈中；或者您可以为其直接静态分配好内存，这样每次重新搜索时就无需重新初始化。但是，一定要注意权衡好初始化存储访问标记的位元数组的开销和使用哈希表的开销，如果在进行搜索时，已访问的节点占到总节点数的比例较小，倒不如使用哈希表的实现。