拓扑排序和强连通分量

我这里参考的书籍是 《[数据结构与算法分析_Java语言描述(第2版)].韦斯》，甚至代码里面的例子都是书里面的。

拓扑排序的一种算法是：

  1. 初始化计算每个节点的入度
  2. 不断地寻找入度为0的节点，记录下来 `res.append(x)`
  3. 然后删除这个节点，并且减少它连接节点的入度
  4. 直到所有节点都被删除，那么 `res` 就是一个拓扑排序。

这个算法非常直观，但是有点开销问题就是需要维护入度这个数据结构（可以使用堆实现），此外也不需要使用递归。 另外一个拓扑排序的实现就是，对有向图进行DFS，先访问孩子然后在访问自己。然后这个顺序的逆序也是一个拓扑排序 

def topsort_dfs(G: Graph):
    # 使用满足拓扑排序要求的顺序进行DFS，之后逆序输出
    # 这些节点就满足拓扑排序要求
    visited = set()
    orders = []
    n = len(G)

    def fn(v):
        visited.add(v)
        for x in range(n):
            if G.mat[v][x] != 0 and x not in visited:
                fn(x)
        orders.append(v)

    for v in range(n):
        if v in visited:
            continue
        fn(v)

    return orders[::-1]

所谓强连通分量(strongly connected component, scc)就是一个图中，对于所有节点对(x,y), 可以从x到y, 也可以从y到x. 强连通分量的求解依赖于上面的拓扑排序，并且可以求解到各个强连通分量。假设我们有图G

  1. 对图G计算拓扑排序
  2. 按照这个拓扑顺序对G'进行DFS

其中G'是G的反向图。每次DFS得到的一个component就是一个scc 

def find_scc(G: Graph):
    # 首先DFS对G里面每个节点进行拓扑排序
    # 然后按照拓扑顺序，对G'(G的反向图)做DFS.
    # 每次得到的一个component就是strongly connected component.

    n = len(G)

    # 先求解拓扑序
    visited = set()
    orders = []

    def dfs_fwd(v):
        visited.add(v)
        for x in range(n):
            if G.mat[v][x] != 0 and x not in visited:
                dfs_fwd(x)
        orders.append(v)

    for v in range(n):
        if v not in visited:
            dfs_fwd(v)

    orders = orders[::-1]

    # 基于拓扑序在反向图遍历
    res = []
    scc = set()
    visited = set()

    def dfs_back(v):
        scc.add(v)
        for x in range(n):
            if G.mat[x][v] != 0 and x not in visited:
                visited.add(x)
                dfs_back(x)

    for v in orders:
        if v not in visited:
            scc = set()
            dfs_back(v)
            res.append(scc)

    return res