9.1 三色标记BFS

  图的BFS和树的BFS搜索大体相同，底层数据结构都是FIFO先进先出队列。但是细节不一样，因为树的重要特性是两个点之前路径是唯一的，不会有重复遍历的可能。而图会有重复访问的可能。如果两个节点同时指向同一个节点，就造成了重复访问，如果图中存在环，那么图的遍历/搜索可能会陷入死循环。为了解决这个问题，必须标记是否已经被访问。那这么说来，没必要使用三色标记，黑白两色就够了一个代表未访问一个代表已访问。在解释为什么要三色之前，我先讲讲三色分别代表什么。
  三色标记如下：
  白色——没有访问
  灰色——被访问但邻居没有被访问
  黑色——被访问而且所有邻居被访问
  其实换成代码是
  白色：还没放入队列
  灰色：放入了队列，但是还没把所有邻居放入队列
  黑色：已经从队列出来了，所有邻居已经放入队列
  三色标记其实是为了提升性能，其实使用到了剪枝策略。

    # 三色标记法
    def bfs_tricolor(self, start, visitor):
        colors = [UnweightedGraph.white for _ in self.__vertices]
        queue = [start]
        colors[start] = UnweightedGraph.gray
        # 距离数组
        d = [0] * len(self.__vertices)
        while len(queue) != 0:
            u = queue.pop(0)
            visitor(u, self.__vertices[u])
            # 遍历邻接矩阵
            # 使用剪枝策略，对黑色节点不做遍历，减少遍历操作
            if colors[u] != UnweightedGraph.black:
                for neighbor in self.__edges[u]:
                    if colors[neighbor] == UnweightedGraph.white:
                        d[neighbor] = d[u] + 1
                        queue.append(neighbor)
                        colors[neighbor] = UnweightedGraph.gray
                colors[u] = UnweightedGraph.black
        return d

  测试用图：

  遍历顺序：

0 A
1 B
2 C
3 D
4 E
7 H
6 G
5 F

  距离数组：

[0, 1, 2, 3, 4, 6, 5, 4]