顶点三染色和时间戳：看CLRS的图遍历

最近在看算法导论的图遍历的章节，发现一个很有趣的事情，在算法导论中，BFS 和 DFS 都有对顶点进行三种染色的实现，并且也添加了时间戳做记录，这让我不禁好奇到底是为什么？于是就有了这篇文章。

BFS

首先我们来看看我们平时通常意义下的 BFS 实现：

def breadth_first_search(graph, s):
    # 创建一个集合用于记录已访问的顶点
    visited = set()
    
    # 标记起始顶点为已访问，并将其加入队列
    visited.add(s)
    queue = deque([s])
    
    # 开始 BFS 遍历
    while queue:
        u = queue.popleft()        
        # 遍历 u 的邻居顶点
        for v in u.Adj:
            if v not in visited:
                visited.add(v)  # 标记为已访问
                queue.append(v)  # 加入队列

很显然，如果一个顶点已经被访问，我们则不加入队列，如果还没被访问，证明还没有被遍历，我们就加入队列。

如果我们使用三染色法呢？

def breadth_first_search(graph, s):
    for u in graph:
        u.color = 'white'
        
    # 访问起始顶点
    s.color = 'gray'
    s.disc = 0
    queue = deque([s])
    
    # 开始 BFS 遍历
    while queue:
        u = queue.popleft()
        # 遍历 u 的邻居顶点
        for v in u.Adj:
            if v.color == 'white':
                v.color = 'gray'
                queue.append(v)
        u.color = 'black'

事实上，对于三种颜色，我们可以把白色看作未被发现的顶点，灰色看作已经被发现正在访问的顶点，黑色看作已经完成访问的顶点。也就是，仅使用 visited 来记录的写法，实际上就是只包含了白色和黑色两种颜色的顶点。

那么灰色呢？灰色的顶点则代表正在队列中的顶点。并且，一旦对一个灰色的顶点访问时，发现其邻居也是灰色顶点，那么就可以做环路检测了。

接下来加上时间戳，就是算法导论中的完整实现：

def breadth_first_search(graph, s):
    for u in graph:
        u.color = 'white'
        u.disc = float('inf')
        u.pre = None
        
    # 访问起始顶点
    s.color = 'gray'
    s.disc = 0
    s.pre = None
    queue = deque([s])
    
    # 开始 BFS 遍历
    while queue:
        u = queue.popleft()
        # 遍历 u 的邻居顶点
        for v in u.Adj:
            if v.color == 'white':
                v.color = 'gray'
                v.disc = u.disc + 1
                v.pre = u
                queue.append(v)
        u.color = 'black

增加了时间戳和前驱顶点，这样就可以看两个顶点之间的最短路径了，我们知道，BFS 的使用场景也更多时在计算顶点之间的最短距离，这样的设计无疑是增加了妙用。

DFS

对于 DFS 也是如此。

通常情况下我们 DFS 的实现是很简单的：

def depth_first_search(graph):
    # 使用集合来记录访问过的顶点
    visited = set()
    for u in graph:
        if u not in visited:
            dfs_visit(graph, u, visited)

def dfs_visit(graph, u, visited):
    # 标记当前顶点为已访问
    visited.add(u)
    
    # 遍历 u 的邻居顶点
    for v in u.Adj:
        if v not in visited:
            dfs_visit(graph, v, visited)

显而易见，我们会一直访问没有访问过的顶点直到尽头。

下面是算法导论中的完整实现：

def depth_first_search(graph):
    global time
    for u in graph:
        u.color = 'white'
        u.pre = None
    time = 0
    for u in graph:
        if u.color == 'white':
            dfs_visit(graph, u)

def dfs_visit(graph, u):
    global time
    # 当顶点 u 被发现
    time += 1
    u.disc = time
    u.color = 'gray'
    
    # 遍历 u 的邻居顶点
    for v in u.Adj:
        if v.color == 'white':
            v.pre = u
            dfs_visit(graph, v)
    time += 1
    u.fin = time
    u.color = 'black'

我们知道树也是图的一种特例，树的先序遍历就相当于图的 DFS，而在树的先序遍历中，除了递归写法还有一种使用栈的写法，所以，灰色的顶点实际上就是在栈中。

并且有了三染色的方法，就可以针对 DFS 去做环路检测以及连通性分析等复杂的操作。

而对于时间戳，也有一个很有趣的地方，就是可以通过这个来看强连通分量，算法导论中有一幅图很好的概括了双时间戳的功能。

总的来说，看似使用三染色和时间戳使得遍历的实现变得复杂了，实际上，图的遍历是处理所有图问题的地基，而三染色和时间戳是后续处理很多图的问题的一种小技巧，现在先将其放进遍历的实现，后续很多问题就可以直接外扩，迎刃而解。