强连接组件

  Sharir-Kosaraju算法,有时候也简称Kosajaru算法，其目的是为了计算出图的强连通分量。强连通分量，英文为strongly connected component，简称SCC。
  首先，我们要先了解什么是强连接分量。强连接分量，是图的一部分，在这一部分里，每个点都可以连接到其他点。如下图（图片来自斯坦福大学），存在五个强连接分量：

  可以看出，强连接分量要么是一个环，要么是几个边相邻的环，要么是两个反向平行边，要么是单独的一个点。而上图覆盖了四种情况。
  求出强连接分量后，可以做什么？首先是可以凝结Condensation。凝结是将强连接分量缩成一个点，这对于大型图简化来说是非常重要的。

Kusajaru算法

  该算法分为三步：
  1. DFS算法计算完成时间。DFS算法可以计算出每个节点的发现时间与完成时间。
  2. 计算逆图，所谓逆图，就是将边进行反向后产生的图。
  3. 在逆图上继续DFS，因为前面正向了，如果反向还能访问，那无疑是一个强连接组件。DFS以最大访问时间的节点开始，如此DFS找出所有的强连接组件。
  以上图为例子，我们先计算访问时间，下图中的括号部分表示的是发现时间与访问时间：

  然后再产生逆图：

  按结束时间从大到小遍历，产生强连通组件，先是E，发现时间戳为26：

  然后是A，发现时间戳为22：

  然后是C，发现时间戳为19：

  然后是K，发现时间戳为12：

  然后是L，发现时间戳为11：

Python实现

# _*_ coding:utf-8 _*_


class UnweightedGraph:
    def __init__(self, vertices, edges):
        self.__vertices = vertices
        self.__edges = edges

    @property
    def vertices(self):
        return self.__vertices

    @vertices.setter
    def vertices(self, value):
        self.__vertices = value

    @property
    def edges(self):
        return self.__edges

    @edges.setter
    def edges(self, value):
        self.__edges = value

    def kosajaru(self):
        # 第一步 DFS计算时间

        time_stack = self.dfs_time_stack()
        # 创建逆图
        reversed_edges = [None] * len(self.__edges)
        # 遍历原图，生成逆图
        for from_vertex, neighbours in enumerate(self.__edges):
            for to_vertex in neighbours:
                if reversed_edges[to_vertex] is None:
                    reversed_edges[to_vertex] = []
                reversed_edges[to_vertex].append(from_vertex)

        # 打印一下逆图
        reversed_graph = UnweightedGraph(self.__vertices, reversed_edges)
        # 对逆图进行DFS
        # scc的列表，是一个二维数组，里面有多个scc，每个scc是一个list
        return UnweightedGraph.dfs_scc(time_stack, reversed_edges)

    white = 0
    gray = 1
    black = 2

    def dfs_time_stack(self):
        # 着色
        colors = [UnweightedGraph.white for _ in self.__vertices]
        times = [{'d': None, 'f': None} for _ in self.__vertices]
        time = 1
        time_stack = []
        for root, _ in enumerate(self.__vertices):
            # 其实可以用栈代替
            if not colors[root] == UnweightedGraph.white:
                continue
            # 这里的i是森林的一个根

            times[root]['d'] = time
            time += 1
            stack = [root]
            while len(stack) > 0:
                # 这一步就错了，不要直接弹出
                v = stack[-1]
                if colors[v] == UnweightedGraph.black:
                    stack.pop()
                    times[v]['f'] = time
                    time += 1

                    time_stack.append(v)
                else:
                    colors[v] = UnweightedGraph.gray
                    for neighbor in self.__edges[v]:
                        if colors[neighbor] == UnweightedGraph.white:
                            times[neighbor]['d'] = time
                            time += 1
                            stack.append(neighbor)
                            colors[neighbor] = UnweightedGraph.gray
                    colors[v] = UnweightedGraph.black


        return time_stack

    @staticmethod
    def dfs_scc(time_stack, edges):
        # 着色
        visited = [False for _ in time_stack]
        # d代表discover f代表finish，发现时间戳和完成时间戳
        scc_list = []
        for root in reversed(time_stack):
            # 其实可以用栈代替
            if visited[root]:
                continue
            # 这里的i是森林的一个根
            stack = [root]
            scc = []
            while len(stack) > 0:
                v = stack.pop()
                if visited[v]:
                    continue
                for neighbor in edges[v]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
                visited[v] = True
                scc.append(v)
            scc_list.append(scc)
        return scc_list

    def to_dot(self):
        s = 'digraph s {\n'
        for v in self.__vertices:
            s += f'"{v}";\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                s += f'\"{self.__vertices[i]}\"->"{self.__vertices[t]}";\n'
        s += '}\n'
        return s

kosaraju算法用来求有向图的强连通分量

我们需要提前知道的知识

什么是强连通

有向图中，从v可以到达w, 从w也可以到达v，那么称v和w是强连通的
如果一副图中任意两点强连通，这幅图也是强连通的。

强连通分量

1. 本图强连通分量为3
   
2. 本图强连通分量为4
   
3. 本图强连通分量为4
   

无向图的连通分量怎么计算

kosaraju算法不过是在下面的基础上增加了几行，

package Algorithm;

public class CC {
    private int count;//连通分量个数
    private boolean[] marked;//标记是否访问过
    private int[] id;//id[v]=1,说明顶点v在分量1里面
    public CC(Graph g){
        marked=new boolean[g.V()];
        id=new int[g.V()];
        for (int i = 0; i <g.V(); i++) {
            if(!marked[i]){
                dfs(g,i);
                count++;
            }
        }
    }
    private void dfs(Graph g,int v){
        marked[v]=true;
        id[v]=count;
        for (int w:g.adj(v)){
            if(!marked[w])  dfs(g,w);
        }
    }
    public boolean connected(int v,int w){
        return id[v]==id[w];
    }
    public int count(){
        return count;
    }
    public int id(int v){
        return id[v];
    }
}

什么是顶点的逆后序排列

调用dfs时，将顶点放在栈里面即可。

package Algorithm.DirectedGraph;
import java.util.LinkedList;
public class DF_Order {
    private LinkedList<Integer>  reversePost;//栈
    private boolean[] marked;//标记是否访问过
    private int vNum;//顶点数目
    public DF_Order(DiGraph g){
        vNum=g.getV();
        reversePost=new LinkedList<>();
        marked=new boolean[g.getV()];
        for (int i = 0; i < g.getV(); i++) {
            if(!marked[i]){
                dfs(g,i);
            }
        }
    }
    private void dfs(DiGraph g, int i) {
        marked[i]=true;
        for(int w:g.adj(i)){
            if(!marked[w]){
                dfs(g,w);
            }
        }
        reversePost.push(i);
    }
    public Iterable<Integer> reversePost(){
        return reversePost;
    }
}

什么是反向图

将有向图的边的指向反过来即可。

反向图：

kosaraju算法

步骤

1. 将图反向
2. 得到反向图的逆后序排列
3. 用逆后序的顺序遍历原图

package Algorithm.DirectedGraph;

public class KosarajuCC {
    private int[] id;
    private int count;
    private boolean[] marked;
    public KosarajuCC(DiGraph graph){
        marked=new boolean[graph.getV()];
        id=new int[graph.getV()];
        DF_Order order = new DF_Order(graph.reverse());
        for (int x:order.reversePost()){
            if(!marked[x]) {
                dfs(graph,x);
                count++;
            }
        }
    }

    private void dfs(DiGraph graph, int v) {
        marked[v]=true;
        id[v]=count;
        for (int x:graph.adj(v)){
            if(!marked[x]) dfs(graph,x);
        }
    }
    public boolean stronglyConnected(int v,int w){
        return id[v]==id[w];
    }
    public int getCount(){
        return count;
    }

}

对于该算法的理解

我们从哪一个顶点进行DFS呢？
按照顶点顺序：0 1 2 3 4 5
那么0 1是一个强连通分量
2 3 4 5是一个强连通分量，显然是不对的。
按照逆后序就是： 0 1 4 5 2 3
那么0 1是一个强连通分量
4 5是一个强连通分量
2 3是一个强连通分量
先访问0 1 4 5，在进行2 3，那么2通向1或4 的道路被封死了。

用这个反向图的逆后序去深度优先搜索(正向)图，可以发现每次递归都是在同一个强连通分量之中。

1. 如图
   
   逆后序得到:0 1 4 5 2 3

2. .
   
   逆后序得到 4 5 2 3 0 1

3. .
   
   逆后序得到 2 3 0 1 4 5

无向图，有向图的图结构

package Algorithm.DirectedGraph;

import Algorithm.Bag;

public class DiGraph {

    private int v;
    private int e;
    private Bag<Integer>[] adj;
    public DiGraph(int v,int e){
        this.v=v;
        this.e=e;
        adj=(Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i]=new Bag<Integer>();
        }
    }
    public DiGraph(int v){
        this.v=v;
        adj=(Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i]=new Bag<Integer>();
        }

    }
    public int getV(){return v;};
    public int getE(){return e;};
    public void add(int v,int w){
        adj[v].add(w);
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
    public DiGraph reverse(){
        DiGraph diGraph = new DiGraph(v);
        for (int i = 0; i < v; i++) {
            for (int x:adj(i)){
                diGraph.add(x,i);
            }
        }
        return diGraph;
    }
}

//无向图
package Algorithm;
public class Graph {
    private int V;
    private int E;
    private Bag<Integer>[] adj;//邻接表
    public Graph(int v,int e) {
        this.V = v;
        this.E=e;
        adj=(Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < V; i++) {
            adj[i]=new Bag<Integer>();
        }
    }
    public Graph(int v){
        this.V=v;
        adj=(Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i]=new Bag<Integer>();
        }
    }
    public int V(){
        //返回定点数
        return V;
    }
    public int E(){
        //返回边数
        return E;
    }
    public void addEdge(int v,int w){
        //添加一条边
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
      //和v相邻的所有顶点。只是输入的时候，不包含计算得出的所有
        return adj[v];
    }
}

package Algorithm;

import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {
    @Override
    public Iterator<Item> iterator() {//实现iterable,才可以foreach
        //iterator 迭代器
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item> {
        private node current=first;
        @Override
        public boolean hasNext() {
            return current!=null;
        }

        @Override
        public Item next() {
            Item item=current.val;
            current=current.next;
            return item;
        }
    }
    private class node{
        Item val;
        node next;
    }
    private int n=0;
    private  node first;
    public void add(Item item){
        node oldfirst=first;
        first=new node();
        first.val=item;
        first.next=oldfirst;
        n++;
    }
    public boolean isEmpty(){
        return first==null;
    }
    public int size(){
        return n;
    }
}

参考自：

1. 知乎：https://www.zhihu.com/question/58926821
2. 算法第四版（橙色）

1、引入

在生活中，可以发现在某些图中，如web底层结构、人际关系网，在图中可以发现高度聚集节点群的算法， 即寻找**“强连通分支Strongly Connected Components”算法。
强连通分支， 定义为图G的一个子集C，C中的任意两个顶点v,w之间都有路径来回**，即(v,w)(w,v)都是C的路径，而且C是具有这样性质的最大子集。
下图是具有3个强连通分支的9顶点有向图
一旦找到强连通分支， 可以据此对图的顶点进行分类， 并对图进行化简。

2、功能分析

（1）转置概念

在用深度优先搜索来发现强连通分支之前， 先熟悉一个概念： Transposition转置，一个有向图G的转置GT，定义为将图G的所有边的顶点交换次序，如将(v,w)转换为(w,v)，可以观察到图和转置图在强连通分支的数量和划分上，是相同的。

（2）Kosaraju算法思路

• 首先， 对图G调用DFS算法， 为每个顶点计算“结束时间”；
• 然后， 将图G进行转置， 得到GT；
• 再对GT调用DFS算法， 但在dfs函数中，对每个顶点的搜索循环里， 要以顶点的“结束时间”倒序的顺序来搜索
• 最后， 深度优先森林中的每一棵树就是一 个强连通分支

以一个例子为例，来阐述以上算法
Step1：第一趟DFS

Step2：转置后第二趟DFS

Step3：深度优先森林结果