算法: 寻找图里的强连通组件

强连通图

先说说图里的强连通组件是什么鬼，在说这个东西之前我们先理解一下强连通图。下面就是一张强连通图。

在强连通图里，每个节点都能通过某条路径访问到所有节点。以上面图为例，0, 1, 2, 3 都能互相访问。

强连通组件

组件就是图中的一部分，由图里的某些节点和边组成。再加上强连通的定义，在这一部分图里每个节点都是可以访问的。具体例子参考下图：

这个图里有 3 个强连通组件，(0, 1, 2)，(3) 和 (4)，注意单个节点也是算一个强连通组件的，因为自己能访问自己嘛。说到这就得提一下强连通组件的一些特点了。

特点

1. 自己连通，就像刚刚所说的自己访问自己。数学语言是存在一个节点 V，V -> V 的路径长度为0
2. 交换特性，如果 V 能通过某条路径访问 W V -> W，那么也可以有一条路径使得 W -> V
3. 传递性，如果 U 能访问 V，且 V 能访问 W U -> V -> W，那么 U 也能访问 W U -> W

寻找强连通组件

我们可以发现强连通组件就算是将它们的边反过来，它还是一个强连通组件。所以我们不禁想到，正向遍历一次再反向遍历一次，如果发现这些节点还是可以互相访问那么就说明这是一个强连通组件了。下面说说具体步骤。

正向遍历

就像刚刚所说的使用 DFS 从图里每个节点去遍历整个图，同时每次访问到一个新节点使用 Stack 去存放这个节点。

当然 DFS 是需要一个额外空间去存放已经访问过的节点。

以上面为例，DFS 结果是 [0, 3, 4, 2, 1]，Stack 里的顺序是 [1, 2, 4, 3, 0]，其中节点 1 在最顶层。

将图取反

遍历完了之后就要将整个图里的边变成相反方向，如下图所示。

反向遍历

还是使用 DFS 去遍历图，但是不同的地方是遍历的根节点不是随机取了，而是从 Stack 里取。每次从 Stack 里弹出一个节点，就对这个节点进行 DFS。如果遍历过程中发现访问到遍历之前的节点说明找到一个强连通组件了。

伪代码

function forwardDFS(vertex, visited) {
    // 已经访问过了
    visited[vertex] = true
    // 遍历子节点
    for (let child in vertex.children) {
        if (!visited[child]) {
            forwardDFS(child, visited)
        }
    }
    Stack.push(vertex)
}

function reverseGraph(oldGraph) {
    let reversedGraph = new Graph
    // 遍历新图的节点
    for (let vertex in reversedGraph.vertices) {
        // 获取旧图里节点的子节点
        for (let child in oldGraph.vertexOf(vertex).children) {
            // 新图节点的子节点就是旧图的父节点 (取反)
            reversedGraph.vertexOf(child).children.push(vertex)
        }
    }

    return reversedGraph
}

function backwardDFS(vertex, visited) {
    visited[vertex] = true
    for (let child in vertex.children) {
        if (!visited[child]) {
            backwardDFS(child, visited)
        }
    }
}

function findSCCs(graph) {
    // 初始化全部都没访问过
    visited = [false]

    // 正向遍历整个图
    for (let vertex in graph.vertices) {
        if (!visited[vertex]) {
            forwardDFS(vertex, visited)
        }
    }

    // 取反整个图
    reversedGraph = reverseGraph(graph)

    // 初始化全部都没访问过
    visited = [false]

    // 按 Stack 顺序去反向遍历
    while (!stack.isEmpty()) {
        let vertex = stack.pop()

        if (!visited[vertex]) {
            backwardDFS(vertex, visited)
        }
    }
}