强连通分量和Kosaraju算法

内容概要：

1. 基于深度优先后序遍历的DAG图拓扑排序
2. 强连通分量
3. 求解强连通分量Kosaraju算法

拓扑排序的另一种方式

求解强连通分量前，来看与之相关的一个求拓扑排序的算法，这个算法基于深度优先后序遍历，所谓深度优先后序遍历，就是在深度优先遍历过程中要在遍历完一个节点的所有相邻节点后才遍历该节点。

DFS后序

当然DFS后序也不一定是唯一的。
基于DFS的拓扑排序算法描述
深度优先后序遍历的逆序就是一个DAG图的拓扑排序结果，这很好理解，DFS后序遍历中后遍历到的一定是先遍历到的节点的前驱。但当图不是DAG图时，我们也能得到这样的一个DFS后序遍历序列以及它的逆序，但这已经不是拓扑排序了，所以该算法不能做环检测。
算法实现
利用实现过的环检测类和DFS类。使用环检测类因为拓扑排序只对DAG图有意义，但该算法本身不能进行环检测。

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class TopoSortPostDFS {
    private Graph G;
    private ArrayList<Integer> res;
    private boolean hasCycle = false;

    public TopoSortPostDFS(Graph G){
        if(!G.directed)
            throw new IllegalArgumentException("TopoSort only works in directed graph!");
        this.G = G;
        res = new ArrayList<>();

        hasCycle = (new DirectedCycleDetection(G)).hasCycle();// 有环则无拓扑序
        if(hasCycle) return;

        GraphDFS dfs = new GraphDFS(G);
        for(int v: dfs.post())
            res.add(v);

        Collections.reverse(res);
    }

    public boolean hasCycle(){
        return hasCycle;
    }
    public ArrayList<Integer> result(){
        return res;
    }

    public static void main(String args[]){
        Graph g = new Graph("g2.txt", true);
        TopoSortPostDFS ts = new TopoSortPostDFS(g);
        System.out.println(ts.result());
    }
}

强连通分量

在有向图中，如果两个顶点间有一条从到的有向路径，同时还有一条从到的有向路径，则称两个顶点强连通。如果有向图的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为的强连通分量(Strongly Connected Components)。

SCC

在上图中，不同的颜色就对应一个强连通分量。
强连通分量求解思路
图G的强连通分量中，同属一个强连通分量的顶点彼此可达，那么如果将每个强连通分量整体看做一个点，就可以得到一个新的抽象有向图。

SCC求解思路

新的有向图一定是一个DAG图，因为两个不同强连通分量之间的顶点一定不彼此可达，否则它们应该构成环，这样它们会属于同一个强连通分量，矛盾。
基于上述思想，如果对新的DAG图按照DFS后序遍历，那么就可以得到新图的拓扑排序的逆序，对应到原图，每个抽象的点就是该点代表的强连通分量。下面要解决的就是如何保证原图的遍历序列一定是连通分量依次遍历的结果，显然单纯的DFS后序遍历不一定能做到这一点，如下图，从0开始DFS后序遍历，2 3 1 0 是一个正确的序列，但不是按连通分量的遍历顺序，我们希望得到的顺序是3 2 1 0这样的。

图G

解决办法就是将原图进行翻转(每条边变反向)，得到对应的反图，这就是Kosaraju算法的核心。
Kosaraju算法
定理：按反图DFS后序遍历序列的逆对原图进行DFS得到的是原图强连通分量拓扑排序的逆(忽略顶点顺序在一个强连通分量看做一个点的抽象图中)。

原图与反图

如在上图中，从0开始，反图的DFS后序序列为1 2 0 3，其逆序为3 0 2 1，这样按照3 0 2 1的顺序对原图进行DFS就可以得到不同的连通分量：3和0 1 2。为了进一步解释正确性，现在再将原图看做反图的反图，从0开始，2 3 1 0 是原图的一个DFS后序序列，其逆序为 0 1 3 2，按照0 1 3 2顺序对反图进行DFS就可以得到不同的连通分量：0 1 2 和3。

利用上述定理，Kosaraju算法只需要求一个图的反图，再按照反图的DFS后序遍历序列的逆序进行DFS即可。由于反图与原图的强连通分量一样，所以对原图进行DFS后序遍历，再按照原图的DFS后序遍历序列的逆序对反图进行DFS也可以。
理解Kosaraju算法的关键是，每个强连通分量中的点在 反图DFS后序序列的逆 中不一定是连续排列的，但 反图DFS后序序列的逆 中，每个连通分量至少有一个点排在前面，这样再按照DFS进行访问一定会遍历整个强连通分量。
Kosaraju算法实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class SCC {

    private Graph G;
    private int[] visited; // 标记顶点是否被访问以及属于哪个连通分量
    private int scccount = 0; // 求连通分量个数

    public SCC(Graph G){
        this.G = G;
        visited = new int[G.V()];
        Arrays.fill(visited, -1);
        GraphDFS dfs = new GraphDFS(G.reverseGraph());
        ArrayList<Integer> order  = new ArrayList<>();
        for(int v: dfs.post())
            order.add(v);

        Collections.reverse(order);

        for(int v : order)
            if(visited[v] == -1) {
                dfs(v, scccount);
                scccount ++; // dfs(v, scccount ++);
            }
    }

    private void dfs(int v, int ccid){// ConnectedComponent ID
        visited[v] = ccid;
        for(int w: G.adj(v))
            if(visited[w] == -1)
                dfs(w, ccid);
    }

    public int count(){
        return scccount;
    }

    public ArrayList<Integer> getCC(){// 查看连通分量标记
        ArrayList<Integer> cc = new ArrayList<>();
        for(int i = 0; i < visited.length; i ++)
            cc.add(visited[i]);
        return cc;
    }

    public ArrayList<Integer>[] components(){
        // 返回各个强连通分量
        ArrayList<Integer>[] res = new ArrayList[scccount];
        for(int i = 0; i < scccount; i ++)
            res[i] = new ArrayList<>();
        for(int v = 0; v < G.V(); v ++)
            res[visited[v]].add(v);
        return res;
    }

    public boolean isStronglyConnected(int v, int w){
        // 判断两个顶点是否互相可达
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v] == visited[w];
    }

    public static void main(String args[]){
        Graph g = new Graph("g2.txt", true);
        SCC cc = new SCC(g);
        System.out.println(cc.count());
        System.out.println(cc.getCC());
        ArrayList<Integer>[] comp = cc.components();
        for(int ccid = 0; ccid < comp.length; ccid ++){
            System.out.print(ccid + ": ");
            for(int w: comp[ccid])
                System.out.print(w + " ");
            System.out.println();
        }
    }
}