9.3是什么颜色_三色标记法?

  图的深度搜索与BFS一样，也是三色标记，基本代码相似，只不过是把FIFO先进先出队列换成FILO先进后出栈。这与树的BFS/DFS是一样的，树也是BFS使用队列，DFS使用栈。阅读本文需要有树的BFS与DFS作为基础，这里我提供我写的树的BFS/DFS博文的链接。python代码如下：

    def dfs_tricolor(self, visitor):
        # 着色
        colors = [UnweightedGraph.white for _ in self.__vertices]
        time = 0
        # d代表discover f代表finish，发现时间戳和完成时间戳
        times = [{'d': None, 'f': None} for _ in self.__vertices]
        stack = [0]
        while len(stack) > 0:
            v = stack.pop()
            time += 1
            if visitor is not None:
                visitor(v, self.__vertices[v])
            times[v]['d'] = time
            if colors[v] != UnweightedGraph.black:
                for neighbor in self.__edges[v]:
                    if colors[neighbor] == UnweightedGraph.white:
                        stack.append(neighbor)
                        colors[neighbor] = UnweightedGraph.gray
            colors[v] = UnweightedGraph.black
            time += 1
            times[v]['f'] = time
        return times

  测试图

  测试图的遍历顺序：

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

  测试图的遍历时的发现时间戳与完成时间戳：

[{'d': 1, 'f': 2}, {'d': 3, 'f': 4}, {'d': 5, 'f': 6}, {'d': 11, 'f': 12}, {'d': 15, 'f': 16}, {'d': 13, 'f': 14}, {'d': 7, 'f': 8}, {'d': 9, 'f': 10}]