数据结构与算法--图论之寻找连通分量、强连通分量

寻找无向图的连通分量

使用深度优先搜索可以很简单地找出一幅图的所有连通分量，回忆连通图的概念：如果从任意顶点都存在一条路径达到任意一个顶点，则称这幅图是连通图。而连通分量指的是一幅图中所有极大连通子图。将整幅图比喻成串了珠子的绳子的话，将任意顶点提起，连通图将是一个整体；非连通图散成若干条较小的整体，这每一条整体就是一个整幅图的一个连通分量。易知连通图只有一个连通分量，就是它自身；如果一幅图的顶点都是分散的，那么连通分量的个数（只有一个顶点）就是图的顶点数个。所以连通分量的数量范围为[1, graph.vertexNum]

下面这幅图，有3个连通分量。

image

回忆深度优先搜索的过程：它从某个顶点出发，访问它的某一个邻接点，接着访问这个邻接点的某一个邻接点....如此深入下去，一直到达某个顶点发现周围的邻接点都已经访问过了，此时往回退到上一个顶点，访问该顶点的未被访问过的邻接点...直到所有顶点都被访问过。很容易知道，在一次深度优先遍历中所有访问过的顶点都是互相可达的，或者说是连通的。我们按照Union-Find算法那样，给每个连通分量标示一个id，即拥有同一个id的顶点归属于同一个连通分量。上面已经分析过，连通分量的数量范围为[1, graph.vertexNum]，所以需要的id个数graph.vertexNum就足够，存储id的数组int[] id的范围是[0, graph.vertexNum - 1]。

下面是寻找无向图的所有连通分量的代码，所用的无向图就是上面那副有3个连通分量的图。

package Chap7;

import java.util.LinkedList;

public class CC {
    // 用来标记已经访问过的顶点，保证每个顶点值访问一次
    private boolean[] marked;
    // 为每个连通分量标示一个id
    private int[] id;
    // 连通分量的个数
    private int count;

    public CC(UndiGraph<?> graph) {
        marked = new boolean[graph.vertexNum()];
        id = new int[graph.vertexNum()];
        for (int s = 0; s < graph.vertexNum(); s++) {
            if (!marked[s]) {
                dfs(graph, s);
                // 一次dfs调用就是一个连通分量，第一个连通分量id为0。
                // 之后分配的id要自增，第二个连通分量的id为1，以此类推
                count++;
            }
        }
    }

    private void dfs(UndiGraph<?> graph, int v) {
        // 将刚访问到的顶点设置标志
        marked[v] = true;
        id[v] = count;
        // 从v的所有邻接点中选择一个没有被访问过的顶点
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }
    }

    public boolean connected(int v, int w) {
        return id[v] == id[w];
    }

    public int id(int v) {
        return id[v];
    }

    public int count() {
        return count;
    }

    public static void main(String[] args) {
        // 边
        int[][] edges = {{0, 6}, {0, 2}, {0, 1}, {0, 5},
                {3, 4}, {3, 5}, {4, 5}, {4, 6}, {7, 8},
                {9, 10}, {9, 11}, {9, 12}, {11, 12}};

        UndiGraph<?> graph = new UndiGraph<>(13, edges);
        CC cc = new CC(graph);
        // M是连通分量的个数
        int M = cc.count();
        System.out.println(M + "个连通分量");
        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M];
        for (int i = 0; i < M; i++) {
            components[i] = new LinkedList<>();
        }
        // 将同一个id的顶点归属到同一个链表中
        for (int v = 0; v < graph.vertexNum(); v++) {
            components[cc.id(v)].add(v);
        }
        // 打印每个连通分量中的顶点
        for (int i = 0; i < M; i++) {
            for (int v : components[i]) {
                System.out.print(v+ " ");
            }
            System.out.println();
        }
    }

}

程序将打印如下信息

3个连通分量
0 1 2 3 4 5 6 
7 8 
9 10 11 12 

对比上图，吻合！

深度优先搜索的应用——判断无向图是否有环

使用DFS可以很方便地判断一幅无向图是否成环（假设不存在自环和平行边）。

package Chap7;

public class UndirectCycle {
    private boolean marked[];
    private boolean hasCycle;

    public UndirectCycle(UndiGraph<?> graph) {
        marked = new boolean[graph.vertexNum()];
        for (int s = 0; s < graph.vertexNum(); s++) {
            if (!marked[s]) {
               // 刚开始没有顶点被访问过，所以当前正访问和上一个被访问的顶点设置为起点s。当dfs被递归调用一次后，当前正访问的参数v是s的一个邻接点，而上一个被访问的参数u是s，符合
                dfs(graph, s, s);
            }
        }
    }
    // 修改过的DFS，v表示当前正访问的顶点，u表示上一个访问的顶点
    private void dfs(UndiGraph<?> graph, int v, int u) {
        // 将刚访问到的顶点设置标志
        marked[v] = true;
        // 从v的所有邻接点中选择一个没有被访问过的顶点
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w, v);
            } else if (w != u) {
                hasCycle = true;
            }
        }
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}

稍微修改了下DFS算法，新增了一个参数u，表示上一个被访问的顶点。判断是否有环，关键就是那句else if (w != u)。注意是w和u比较。为什么这样就能判断有环了呢？如果当前访问的顶点v的这个邻接点w是之前已经访问过的，且不是上一个访问的顶点，那么该无向图就有环。也就是下图这种情况。

image

w已经被访问过且w == u的情况，无环。也就是下图的情况

image

寻找有向图的强连通分量

在一幅有向图中，如果两个顶点v和w是互相可达的，则称它们是强连通的。如果一幅有向图中任意两个顶点都是强连通的，那么这幅图也是强连通的。

有向环和强连通有着紧密的关系，两个顶点是强连通的当且仅当它们都在一个普通的有向环中。这很容易理解，存在v -> w的路径，也存在w -> v的路径，则v和w是强连通的，同时也说明了这是一个环结构。一个含有V个顶点的有向图，含有的强连通分量的个数范围为[1, V]——强连通图只有一个强连通分量，而一个有向无环图中则含有V个强连通分量。

下图中就含有5个强连通分量。

image

和计算无向图中的连通分量一样，计算有向图的强连通分量也是深度优先搜索的一个应用。只需在上面代码的基础上加上几行，即可实现这个称为Kosaraju的算法。

这个算法虽然实现简单，但是并不好理解。nullzx的博客园这篇博文讲得很好，看完后算是理解了Kosaraju算法那神奇的做法...

image

上图是一个含有两个强连通分量的有向图。强连通分量和强连通分量之间不会形成环，否则这两个连通分量就是一个整体，即看成同一个强连通分量。如果将连通分量缩小成一个顶点，那么上图就是一个含有两个顶点的无环图，且左边的顶点指向了右边的顶点。

如果从左边的强连通分量中任意一个顶点开始DFS，那么只需一次调用就能访问到图中所有顶点，这主要是因为两个连通分量之间A2指向B3；相反，从右边的强连通分量中任意一个顶点出发深度优先搜索，需要调用DFS两次——这正好是强连通分量的个数，而且每一次调用DFS访问的顶点就是一个强连通分量中的所有顶点（先假设这句话是正确的，下面会给出这个命题的证明），比如第一次调用DFS，访问了B3、B4、B5，这三个顶点恰好组成右边强连通分量的所有顶点。反过来想，为了找出全部的强连通分量，保证DFS访问顶点的顺序为B强连通分量中任意一个顶点在A强连通分量全部顶点之前即可。或者换个角度思考，将连通分量缩小成顶点后，整个图变成了无环图，DFS访问顶点的顺序是：先访问那些不指向任何连通分量（顶点）的顶点，比如上面A2指向B3，所以应该先访问B中的顶点。说得更通俗点也就是，DFS将先访问出度为0的那些连通分量（看成一个顶点），这样能保证一次调用DFS肯定是在同一个连通分量里面递归，不会跑到其他连通分量中取。如果先访问那些指向了其他分量（出度不为0）的分量，DFS一定能进入到其他连通分量中，如A连通分量通过A2进入到B连通分量中，这样的话，一次DFS遍历了多个强连通分量，根本就达不到目的。

如B3, A2, A0, A1, B4, B5，按照这个序列调用DFS，就能保证DFS一定会被调用两次。当然序列是不唯一的，在DFS中有一种常见的序列可以保证这种关系，即逆后序。

所谓逆后序就是在DFS递归调用返回之前，将该顶点压入栈中得到的序列。例如dfs(s) -> dfs(v)这个递归调用栈，表示了一条s -> v的路径，v将比s先返回，故先存入v，再存入s，栈中的顺序是sv。

现在可以说说Kosaraju算法的思路：

• 将原图取反。
• 对反向图作深度优先遍历，得到顶点的逆后序排列。
• 回到原图，按照上面得到的逆后序序列的顺序，对原图进行深度优先搜索。（而不是按照0, 1, 2...这样的顶点顺序）

我们来看，为什么反向图的逆后序就是我们需要的序列。

image

上图是取反后的有向图。设原图为G，取反后的图为Gr。深度优先搜索Gr有两种可能：

• 从强连通分量A中任意一个顶点开始，需要调用两次DFS，第一次A0、A1、A2入栈；第二次B3、B4、B5入栈。这种情况下，强连通分量B所有顶点都在强连通分量A之前。
• 从强连通分量B中的任意一个顶点开始，只需调用一个DFS即可遍历到所有顶点。由于是逆后序，因为B中最先被访问的顶点，最后才会返回，因此它在栈中位于栈顶的位置。

上面两种情况都保证了B中至少有一个顶点在A全部顶点之前，回到原图中就会先对B中的顶点先进行DFS。推广到拥有多个强连通分量的有向图，上述推论依然是成立的。

反向图的逆后序实际上是它的一个伪拓补序列（“伪”是因为可能有环结构），将连通分量缩小成一个顶点后，有向图无环了，反向图的逆后序就成了一个拓补序列——入度为0的顶点的总是排在前面。则在原图中，该拓补序列就变成了出度为0的顶点排在前面了，上面有分析到，对那些出度为0的分量（已看作顶点）先进行DFS的话，就可以保证每一次调用DFS访问的顶点都处于同一个强连通分量下。

要确切地证明Kosaraju算法的正确性，需要证明这个命题：按照反向图的逆后序顺序在原图中进行DFS，每一次DFS中所访问的所有顶点都在同一个连通分量之中。上面说了这么多，只是定性解释了为什么使用反向图的逆后序这样的序列可以达到目的，命题的后半句...在上面的分析中我们假设它是正确的，实际上这个命题需要严格的证明，下面就来证明在命题前半句的前提下，后半句的正确性。

要证明这个命题，有两点需要证明（按照反向图逆后序的顺序进行DFS的前提下）：

• 每个和s强连通的顶点v必然会在调用dfs(G, s)中被访问到；
• dfs(G, s)所达到的任意顶点v都必然是和s强连通的。

第一点，用反证法：假设存在一个顶点v不是在调用dfs(G,s)中被访问到的，因为存在s -> v的路径，说明v在调用dfs(G, s)之前就已经被访问过了（否则和假设不符）；又因为也存在v -> s的路径，所以在调用dfs(G , v)后，s肯定也会被标记已访问，这样就调用不到dfs(G ,s)了，与我们假设会调用dfs(G, s)的前提矛盾了。所以原命题成立。

第二点，dfs(G, s)能达到顶点v，说明存在s -> v的路径，要证明s和v是强连通的，只需再证明在原图G中还存在一条v -> s的路径，等价于在反向图Gr中找到一条s -> v的路径。由于是按照逆后序进行深度优先搜索，在Gr中dfs(Gr, v)一定是在dfs(Gr, s)之前返回的，否则逆后序就变成了[v, s]，原图在dfs调用时就会先调用dfs(G, v)，此时如果原图存在v -> s的路径，那么dfs(G, v)被调用后，s会被标记已访问，从而dfs(G, s)不会被调用到——这和我们假设的前提dfs(G, s)会被调用且达到v顶点矛盾。所以在Gr中dfs(Gr, v)一定会在dfs(Gr, s)之前返回，这有两种情况

• dfs(Gr, v)在dfs(Gr, s)之前调用，并且也在dfs(Gr, s)的调用结束前结束。即dfs(Gr, v)调用 -> dfs(Gr, v)结束 -> dfs(Gr, s)调用 -> dfs(Gr, s)结束
• dfs(Gr, v)在dfs(Gr, s)之后调用，并且在dfs(Gr, s)的调用结束前结束。即dfs(Gr, s)调用 -> dfs(Gr, v)调用 -> dfs(Gr, v)结束 -> dfs(Gr, s)结束

第一种情况是不可能的。因为Gr中存在v -> s（G中有s -> v），所以第一种情况中的调用不可能出现。第二种情况恰好说明了Gr中存在一条s -> v的路径。得证！

如下，中间和右侧的图对应着上面两种情况。

image

证明也证明了，代码该给出了。

package Chap7;

import java.util.LinkedList;

/**
 * 寻找有向图中的强连通分量
 */
public class KosarajuSCC {
    // 用来标记已经访问过的顶点，保证每个顶点值访问一次
    private boolean[] marked;
    // 为每个连通分量标示一个id
    private int[] id;
    // 连通分量的个数
    private int count;

    public KosarajuSCC(DiGraph<?> graph) {
        marked = new boolean[graph.vertexNum()];
        id = new int[graph.vertexNum()];
        // 对原图G取反得到Gr
        DFSorder order = new DFSorder(graph.reverse());
        // 按Gr的逆后序进行dfs
        for (int s : order.reversePost()) {
            if (!marked[s]) {
                dfs(graph, s);
                // 一次dfs调用就是一个连通分量，第一个连通分量id为0。
                // 之后分配的id要自增，第二个连通分量的id为1，以此类推
                count++;
            }
        }
    }

    private void dfs(DiGraph<?> graph, int v) {
        // 将刚访问到的顶点设置标志
        marked[v] = true;
        id[v] = count;
        // 从v的所有邻接点中选择一个没有被访问过的顶点
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }
    }

    public boolean stronglyConnected(int v, int w) {
        return id[v] == id[w];
    }

    public int id(int v) {
        return id[v];
    }

    public int count() {
        return count;
    }

    public static void main(String[] args) {
        // 边
        int[][] edges = {{0, 1}, {0, 5}, {2, 3},{2, 0}, {3, 2},
                {3, 5}, {4, 2}, {4, 3},{4, 5}, {5, 4}, {6, 0}, {6, 4},
                {6, 9}, {7, 6}, {7, 8}, {8, 9},{8, 7}, {9, 10},
                {9, 11}, {10, 12}, {11, 4}, {11, 12}, {12, 9}};

        DiGraph<?> graph = new DiGraph<>(13, edges);
        KosarajuSCC cc = new KosarajuSCC(graph);
        // M是连通分量的个数
        int M = cc.count();
        System.out.println(M + "个连通分量");
        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M];
        for (int i = 0; i < M; i++) {
            components[i] = new LinkedList<>();
        }
        // 将同一个id的顶点归属到同一个链表中
        for (int v = 0; v < graph.vertexNum(); v++) {
            components[cc.id(v)].add(v);
        }
        // 打印每个连通分量中的顶点
        for (int i = 0; i < M; i++) {
            for (int v : components[i]) {
                System.out.print(v + " ");
            }
            System.out.println();
        }
    }
}

针对一幅具体的有向图，我们来看看Kosaraju算法的轨迹。左侧的图是对反向图作DFS，得到逆后序排列是一个伪拓补序列；在右侧的图中，原有向图按照这个序列进行DFS，总共对5个顶点进行了DFS，每次DFS都表示一个强连通分量（方框框起来的顶点集合）。

[图片上传失败...(image-f58914-1510374691562)]

上面代码中的测试样例其实就是上面这个图。它会打印如下信息

5个连通分量
1 
0 2 3 4 5 
9 10 11 12 
6 
7 8 

对比上图方框圈起来的内容，的确实是5个强连通分量。

顺便一提，如果将图中的强连通分量缩小成一个顶点，就能得到下图。因为强连通分量和强连通分量之间不会形成环，所以逆后序得到的是真正的拓补序列。回到原有向图中，按照该拓补序列顺序DFS（顺序是1, 0, 11, 6, 7），可以发现算法总是优先选择出度为0的顶点，进行DFS后删除该顶点，再从剩余的图中选择出度为0的顶点继续DFS。

image

对该算法的分析我都觉得蛋疼...嫌麻烦的直接记住结论即可。

by @sunhaiyu

2017.11.1