SCC算法初解

发表于 分类于 阅读次数： 本文字数： 6.2k 阅读时长 ≈ 8 分钟

在算法学习之路上漂泊，遇见了图，而分无向与有向。在本文中主要讲解关于有向图中的求极大连通分量的算法，主要是Kasaraju算法、Tarjan算法以及Gabow算法。

三种算法都是基于深度优先搜索算法（DFS）而实现的，实际上后两种算法是对于Kasaraju算法的改进，减少了一次深度优先搜索（DFS），因此在性能上相比较而言要好一些。

初识强连通分量

首先，连通分量是无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(Va,Vb)，皆存在路径Va→Vb以及Vb→Va。强连通分量则是指一张有向图G的极大强连通子图G’。如果将每一个强连通分量缩成一个点，则原图G将会变成一张有向无环图。一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量，因为有向环即是一个强连通分量，而且任何的强连通分量皆具有至少一个有向环。（摘自维基百科）

对于无向图，求连通分量的问题就等价于求是否连通的问题，使用深度优先、广度优先搜索的算法的到的树都能求出最大连通分量。

Kasaraju算法

Kasaraju算法在我第一次接触时，感觉确实有点难理解，虽然现在也还是有点难理解。本文中不会去证明算法，只是讲解算法的一些实现等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public static class KosarajuSCC {
    int n;
    List<Integer>[] adj;

    KosarajuSCC(int n) {
        this.n = n;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            this.adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        this.adj[v].add(w);
    }

    //正向遍历，以后根序压栈，保证根先出栈
    public void fillorder(int v, boolean[] visited, Stack<Integer> s) {
        visited[v] = true;
        for (Integer i : this.adj[v]) {
            if (!visited[i]) {
                fillorder(i, visited, s);
            }
        }
        s.push(v);
    }

    //reverse 得到反向图
    public KosarajuSCC getTranspose() {
        KosarajuSCC gv = new KosarajuSCC(this.n);
        for (int i = 0; i < n; i++) {
            for (Integer j : this.adj[i]) {
                gv.adj[j].add(i);
            }
        }
        return gv;
    }

    //DFS打印连通分支
    public void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
        for (Integer i : adj[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }

    //按照Kosaraju算法的步骤执行
    public void printSCCs() {
        Stack<Integer> s = new Stack<Integer>();
        boolean[] visited = new boolean[this.n];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        //逆后序压栈
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                fillorder(i, visited, s);
            }
        }
        //得到反向图
        KosarajuSCC gr = this.getTranspose();
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        //依据反向图算可达性
        while (!s.empty()) {
            int v = s.pop();
            if (visited[v] == false) {
                gr.DFSUtil(v, visited);
                System.out.println();
            }
        }
    }
}

先理解一下Karasaju算法的思路。

Kasaraju算法

  • 对图G求其逆后序，即在深度优先遍历（DFS）中在递归调用之后压入栈中；
  • 对G进行转置，在代码中即得到反图；
  • 按照第一步中得到的栈的出栈的顶点顺序，对于GR图进行DFS可以得到若干搜索树。每棵搜索树都代表一个强连通分量。

示例图G

如上图示例的有向图，先求逆后序排序，得到{7, 8, 6, 9, 11, 10, 12, 0, 5, 4, 2, 3, 1}，然后按照这个图的转置图GR进行DFS，最终可以得到极大强连通分量5个：{7, 8}, {6}, {9, 11, 10, 12}, {0, 5, 4, 2, 3}, {1}。

在Karasaju算法中使用了两次DFS，第一次是得到节点的逆后序排序（有的算法书将逆后序排序合并在拓扑排序里面）；第二次是对于转置图DFS得到最终的强连通分量。我们当然想要对于算法进行优化，减少DFS的次数也是一种极好的优化方式，想想如果一次DFS就可以得出强连通分量岂不是很好。

Tarjan算法

Tarjan算法是对于Kasaraju算法的改进。其基本代码实现思维如下：

  • 遍历一个点，指定唯一时间戳DFN[i]；指定改点向前追溯可追溯到最老时间戳LOW[i]；
  • 枚举当前点的所有边，若DFN[j]=0表明未被搜索过（这儿0、-1等都是可以的，只要是自我约定好的，正常不使用的就可以，如下面算法中使用的NO_VISIT），递归搜索；
  • 当DFN[i]不为0，则j被搜索过，这时判断是否在我们存储新建的栈中，且j的时间戳DFN[j]小于当前时间戳DFN[i]，可判定成环，将LOW[i]设定为DFN[j]；
  • 若这个点LOW[i]和DFN[i]相等，则这个点是目前强连通分量的元素中在栈中的最早的节点；
  • 出栈，将这个强连通分量全部弹出，保存。

Tarjan算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public static class TarjanSCC {
    private int numOfNode;
    private List<ArrayList<Integer>> graph;//二维数组表示图
    private List<ArrayList<Integer>> result;//保存极大强连通图
    private boolean[] inStack;//标记节点是否在栈内
    private Stack<Integer> stack;
    private int[] dfn;
    private int[] low;
    private int time;//当前时间戳（实际是一个int的数，标记当前访问的节点）
    private static final int NO_VISIT = 0;

    public TarjanSCC(List<ArrayList<Integer>> graph, int numOfNode) {
        this.graph = graph;
        this.numOfNode = numOfNode;
        this.inStack = new boolean[numOfNode];
        this.stack = new Stack<Integer>();
        dfn = new int[numOfNode];
        low = new int[numOfNode];

        Arrays.fill(dfn, NO_VISIT);//将dfn所有元素都置为0，代表i还有没被访问过。
        Arrays.fill(low, NO_VISIT);
        result = new ArrayList<ArrayList<Integer>>();
    }

    //获取强连通分量
    public List<ArrayList<Integer>> tarjanResult() {
        for (int i = 0; i < numOfNode; i++) {
            if (dfn[i] == NO_VISIT) {
                tarjan(i);
            }
        }
        return result;
    }

    //算法核心
    public void tarjan(int current) {
        dfn[current] = low[current] = time++;
        inStack[current] = true;
        stack.push(current);

        for (int i = 0; i < graph.get(current).size(); i++) {
            int next = graph.get(current).get(i);
            if (dfn[next] == NO_VISIT) {
                tarjan(next);
                low[current] = Math.min(low[current], low[next]);
            } else if (inStack[next]) {
                low[current] = Math.min(low[current], dfn[next]);
            }
        }

        if (low[current] == dfn[current]) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            int j = -1;
            while (current != j) {
                j = stack.pop();
                inStack[j] = false;
                temp.add(j);
            }
            result.add(temp);
        }
    }
}

需要注意的是在算法中的时间戳这个标记，并不是代表真正的时间戳，而是对于每个节点不同的一种标记，在本文算法中都是用一个递增数组来表示，即访问每个节点时，将该时间戳变量自增赋值给该节点的时间戳DFN[i]。

Gabow算法

Gabow算法在基础上与Tarjan算法相似，都是利用一次DFS算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public static class GabowSCC {
    private int numOfNode;
    private List<ArrayList<Integer>> graph;//二维数组表示图
    private List<ArrayList<Integer>> result;//保存极大强连通图
    private Stack<Integer> path;
    private Stack<Integer> root;
    private int[] order;
    private int time;//当前时间戳（实际是一个int的数，标记当前访问的节点）
    private static final int NO_VISIT = -1;
    private int[] part; // 连通变量的标号；
    private int partNum = 0;

    public GabowSCC(List<ArrayList<Integer>> graph, int numOfNode) {
        this.graph = graph;
        this.numOfNode = numOfNode;
        this.path = new Stack<>();
        this.root = new Stack<>();
        order = new int[numOfNode];
        part = new int[numOfNode];

        Arrays.fill(order, NO_VISIT);
        Arrays.fill(part, NO_VISIT);
    }

    public int[] gabowResult() {
        for (int i = 0; i < numOfNode; i++) {
            if (order[i] == NO_VISIT) {
                gabow(i);
            }
        }
        return part;
    }

    public void gabow(int v) {
        order[v] = ++time;
        path.push(v);
        root.push(v);

        for (int i = 0; i < graph.get(v).size(); i++) {
            int next = graph.get(v).get(i);
            if (order[next] == NO_VISIT) {
                gabow(next);
            } else if (part[next] == NO_VISIT) {
                while (order[root.peek()] > order[next]) {
                    root.pop();
                }
            }
        }

        if (v == root.peek()) {
            root.pop();
            partNum++;
            int top;
            do {
                top = path.peek();
                part[top] = partNum;
                path.pop();
            } while (top != v);
        }
    }
}

其算法基本思路是：

Gabow算法

  • 在所有顶点中，找一个没有被访问的节点v，如果没有则完成；
  • 记录v的访问顺序；
    将v压入堆栈path和root；
    如果v指向的邻接点，对应每个邻接点next：
    1、如果没有访问过，则以next为参数，递归到第二步；
    2、如果访问过，且没有确定它属于哪个强连通分量，弹出root栈中next之后（即之上）的所有顶点；
    3、如果root栈中的元素等于v，那么在part中记录顶点对应的强连通分量
  • 递归返回

附

本文只涉及算法的实现，没有设计算法的证明等，如有想法，请分享。