有向图算法

之前接触过的图都是无向图，在这个小节中讲解有向图

实际生活中的很多问题都可以建模为一个有向图的模型：

• 社交网络：图中的节点看做是一个个的人，如果一个节点指向一个节点，表示这个人关注了这个人，这种关注关系是有方向的
• 学习课程：将图中的节点看做是一门门的课程，一门课程被其他课程所指向，表示学习这门课程之前需要学习其他的课程，这种学习顺序也是有指向关系的
• 模块引用：将图中的节点看做是一个个的程序模块，一个模块被其他模块指向，表示该模块依赖于其他模块，这种模块之间的依赖也是有方向的

有向图的表示

我们之前介绍的无向图可以看做是一种特殊的有向图，所谓的特殊在于每个节点都互相指向。我们之前在 g.txt 值规定规定了节点之间的连接关系，所以我们当我们读取到下面的形式的时候

0 1

表示的是节点 0 指向节点 1 以及节点 1 指向节点 0，所以我们在无向图中实现如下

adj[0].add(1);
adj[1].add(0);

如果我们只是想表示节点 0 指向节点 1，我们就不需要添加下面那一行语句就好了。所以有向图对比于无向图的实现只需要更改这一个部分

{48}

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.TreeSet;

public class DirectedGraph {
    private int E;
    private int V;
    private TreeSet<Integer>[] adj;

    public DirectedGraph(String filename) {
        File file = new File(filename);
        Scanner scanner = null;
        try {
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            if (this.V < 0) {
                throw new IllegalArgumentException("V Must Be Positive");
            }

            this.adj = new TreeSet[this.V];
            for (int i = 0; i < this.V; i++) {
                this.adj[i] = new TreeSet<>();
            }

            this.E = scanner.nextInt();
            if (this.E < 0) {
                throw new IllegalArgumentException("E Must Be Positive");
            }

            this.inDegree = new int[V];
            this.outDegree = new int[V];

            for (int i = 0; i < this.E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                if (a == b) {
                    throw new IllegalArgumentException("Self loop exists");
                }
                if (adj[a].contains(b)) {
                    throw new IllegalArgumentException("Parallel edge exists");
                }

                // 只是删掉了 adj[b].add(a)
                adj[a].add(b);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    private void validateVertex(int v) {
        if (v < 0 || v >= this.V) {
            throw new IllegalArgumentException("Vertex " + v + " is invalid");
        }
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int v = 0; v < this.V; v++) {
            stringBuilder.append(String.format("%d : ", v));
            for (int w: adj(v)) {
                stringBuilder.append(String.format("%d ", w));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }
}

需要注意的是有一个概念同无向图有所不同，那就是度的概念，在有向图中度分为两类：

• 入度：有多少条边指向该节点
• 出度：有多少条件从该节点指向别的节点

例如对于下图，节点 2 的入度为 2，因为有两条边指向节点 2，出度为 1，因为有一条边从它指向节点 4。

所以我们再次修改一下类 DirectedGraph 如下

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.TreeSet;

public class DirectedGraph {
    private int E;
    private int V;
    private TreeSet<Integer>[] adj;

    // 增加入度和出度的成员变量
    private int[] inDegree;
    private int[] outDegree;

    public DirectedGraph(String filename) {
        File file = new File(filename);
        Scanner scanner = null;
        try {
            // 其他代码相同

            this.inDegree = new int[V];
            this.outDegree = new int[V];

            for (int i = 0; i < this.E; i++) {
                // 其他代码相同

                adj[a].add(b);
                // 在这里初始化入度和出度，a → b，a的出度增加，b的入度增加
                inDegree[b]++;
                outDegree[a]++;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    public int inDegree(int v) {
        validateVertex(v);
        return inDegree[v];
    }

    public int outDegree(int v) {
        validateVertex(v);
        return outDegree[v];
    }

    // 其他方法
}

DFS

对于有向图来说，它的 DFS 代码和 BFS 代码同无向图的写法完全是一样的，因为在后文中需要用到 DFS 遍历，所以这里贴出有向图的 DFS 遍历代码

import java.util.ArrayList;

public class DFSDirectedGraph {
    private DirectedGraph graph;
    // 深度优先前序遍历结果
    private ArrayList<Integer> pre;
    // 深度优先后序遍历结果
    private ArrayList<Integer> post;
    private boolean[] visited;

    public DFSDirectedGraph(DirectedGraph graph) {
        this.graph = graph;
        this.pre = new ArrayList<>();
        this.post = new ArrayList<>();
        this.visited = new boolean[graph.V()];

        for (int v = 0; v < graph.V(); v++) {
            if (!visited[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int v) {
        visited[v] = true;
        pre.add(v);
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
        post.add(v);
    }

    public ArrayList<Integer> pre() {
        return pre;
    }

    public ArrayList<Integer> post() {
        return post;
    }
}

可见上面的代码与无向图的 DFS 并无不同。

有向图的环检测

检测有向图中是否存在环是一件很有必要的事情

如果将上面的图看做是一个课程之间的依赖关系，如果图中存在环，说明课程之间相互依赖，学习课程 A 之前需要先学习课程 B，而学习课程 B 之前又需要先学习课程 A，这样的学习顺序肯定是有问题的。

我们想一想我们在无向图中是怎么做环检测的，我们使用 DFS 遍历，当遍历到一个节点时，如果某个邻接节点已经被访问了，并且不是它的父亲节点，我们就可以认为图中存在一个环。但是对于有向图就不一样了

上面的动图是优先遍历的顺序，最后我们来到了节点 3

此时我们发现节点 3 的相邻节点 2 已经被访问过了，并且节点 2 不是 3 的上一个节点，但是我们能说图中存在一个环吗? 不能，因为节点 2 无法到达节点 3，所以形成不了一个环。

此时我们需要另外一个变量来表示节点是否在路径上，如果一个节点访问邻接节点时发现该节点已经被访问过且在路径上，我们就可以说构成了一个环。

什么叫在路径上，如果这个节点还没有回溯到上一个节点，我们就说这个节点在路径上。

如果我们在访问到节点 w 时，节点 v 还在路径上，说明节点 v 可以到达节点 w，如果此时节点 w 可以到达节点 v 不就说明存在一个环吗。

public class DirectedCycleDetect {
    private DirectedGraph graph;
    private boolean[] visited;
    // onPath[w] 表示节点 w 是否在路径上
    private boolean[] onPath;
    private boolean hasCycle;

    public DirectedCycleDetect(DirectedGraph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.V()];
        this.onPath = new boolean[graph.V()];
        this.hasCycle = false;

        for (int v = 0; v < graph.V(); v++) {
            if (!visited[v]) {
                if (dfs(v)) {
                    hasCycle = true;
                    break;
                }
            }
        }
    }

    private boolean dfs(int v) {
        visited[v] = true;
        onPath[v] = true;
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                if (dfs(w)) {
                    return true;
                }
            // 通无向图不同，2 -> 1 -> 2 也是一个环
            } else if (onPath[w]) {
                return true;
            }
        }
        // 回溯到上一个节点时就不在路径上了
        onPath[v] = false;
        return false;
    }

    public boolean isHasCycle() {
        return hasCycle;
    }
}

拓扑排序

还是对于下面的这么一副图

假设上面的节点代表一门课程的话，我们想知道应该以什么样的顺序学习所有的课程，这其实就是在寻找图的拓扑排序。

那么我们寻找图的拓扑排序呢? 还是以学习课程举例，要学习一门课，那么这门就不能依赖于任何一门其他的课，或者这门课已经被学过了，就比如上面我们应该先学习课程 0，因为没有任何课程指向它，它不依赖于任何课程，以图论的语言来说，因为节点 0 的入度为 0，所以先学习课程 0。

学习完课程 0 之后，为了表示这门课程已经学过，我们将依赖于节点 0 的节点的入度减一

接下来我们应该学习哪门课呢? 当然是入度为 0 的课，表示不需要前置课程或者前置课程已经学过了，所以我们接下来学习课程 1，并且将依赖课程 1 的其他课程的入度减一

接下来还是学习入度为 0 的课程，即课程 3，并且更新依赖课程 3 的其他课程的入度

接着学习课程 2，因为它的入度为 0，然后更新依赖课程 2 的其他课程的入度

最后学习课程 4

所以最终课程的学习顺序为 0 → 1 → 3 → 2 → 4，也就是拓扑排序的结果。

所以我们对图做拓扑排序，就重复做两步：

• 选择入度为 0 的节点
• 更新相邻节点的入度

另外一个需要注意的问题就是，拓扑排序只对有向无环图(DAG) 有效，如果图中有环，二者相互依赖，就不知道先学习哪一门课程了。

在代码的实现方面，我们使用队列来存储入度为 0 的节点，在更新相邻节点入度的时候，如果入度为 0 则添加进队列中，每次从队列取出一个值时，我们添加到一个 List 中，表示拓扑排序的顺序。另外如果图中存在环的话，那么这个 List 中保存的节点数目肯定小于整个图的节点数目，此时可以使用拓扑排序来做环检测。

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

public class TopoSort {
    private DirectedGraph graph;
    private int[] inDegree;
    private ArrayList<Integer> result = new ArrayList<>();
    private boolean hasCycle = false;

    public TopoSort(DirectedGraph graph) {
        this.graph = graph;
        this.inDegree = new int[graph.V()];

        Queue<Integer> queue = new LinkedList<>();
        for (int v = 0; v < graph.V(); v++) {
            inDegree[v] = graph.inDegree(v);
            if (inDegree[v] == 0) {
                queue.add(v);
            }
        }

        while (!queue.isEmpty()) {
            int v = queue.remove();
            result.add(v);
            for (int w: graph.adj(v)) {
                inDegree[w]--;
                if (inDegree[w] == 0) {
                    queue.add(w);
                }
            }
        }

        if (result.size() != graph.V()) {
            hasCycle = true;
            result.clear();
        }
    }

    public boolean isHasCycle() {
        return hasCycle;
    }

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

此时我们在介绍一种拓扑排序的算法，它需要借助于深度优先后序遍历。回顾一个后序遍历的概念，后序遍历指的是先访问完相邻节点，然后访问自己。

对于有向图意味着什么，意味着先访问依赖自己的节点，然后访问自己，说明自己是在依赖于自己的节点之后访问的，如果我们对深度优先后序遍历做一个逆序，这个顺序就表示自己在依赖于自己的节点之前被访问的，这不就是拓扑排序的结果吗。

使用深度优先后序遍历有一个缺点就是它不能做环检测，虽然图中有环，但是还是能够深度优先后序遍历，只不过此时结果便没有意义了。所以在使用这个方法做拓扑排序之前，我们需要使用我们之前讲解的有向图的环检测算法进行环检测

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

public class TopoSort2 {
    private DirectedGraph graph;
    private boolean hasCycle;
    private ArrayList<Integer> result = new ArrayList<>();

    public TopoSort2(DirectedGraph graph) {
        this.graph = graph;
        // 使用之前的讲解的环检测类进行环检测
        DirectedCycleDetect directedCycleDetect = new DirectedCycleDetect(graph);
        this.hasCycle = directedCycleDetect.isHasCycle();

        if (hasCycle) {
            return;
        }

        // 对图做深度优先后序遍历
        DFSDirectedGraph dfsDirectedGraph = new DFSDirectedGraph(graph);
        for (int v: dfsDirectedGraph.post()) {
            result.add(v);
        }
        // 对后序遍历取逆序
        Collections.reverse(result);
    }

    public boolean isHasCycle() {
        return hasCycle;
    }

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

强连通分量

现在还有一个问题就是我们怎么检测图中有多少个强联通分量，以及每一个强联通分量中包含哪些节点。所谓的强联通分量指如果某些节点互相可达，那么这些节点就组成了一个强联通分量。

如上图就三个强联通分量，每个联通分量内部的节点都是互相可达的。

在求解有向图的联通分量之前，我们回顾一下无向图的联通分量是如何求解的，我们从任意一个节点开始做 DFS，每次做一次 DFS 就表示有一个联通分量

for (int i = 0; i < visited.length; i++) {
    if (!visited[i]) {
        cccount++; // 联通分量个数增加
        dfs(i);
    }
}

但是对于有向图我们能从任意一个节点开始吗? 答案是不行，而是要以特定的顺序遍历。如果我们将一个个的联通分量看做是一个图中的节点

如果我们分别遍历联通分量 $E \rightarrow C \rightarrow A \rightarrow D \rightarrow B$ 中的节点，那么每做一次 DFS 就就可以统计联通分量数目，那么为什么会是上面的顺序呢?

为什么从 $E$ 开始遍历，因为 $E$ 只依赖其他联通分量的节点，没有其他联通分量依赖于它，所以从 $E$ 中的某个节点做 DFS，只能遍历到联通分量 $E$ 中的节点。同理遍历完了 $E$，此时 $C$ 也只依赖于其他联通分量，虽然 $E$ 依赖于 $C$，但是 $E$ 已经遍历完毕了，所以此时从 $C$ 中的节点开始做 DFS 只能遍历到 $C$ 中所有的节点，剩余的也是同理。

也就是说依赖于自己的联通分量要被先遍历到，也就是相邻节点要在自己之前被访问到，其实就是深度优先后序遍历的顺序，所以 $E \rightarrow C \rightarrow A \rightarrow D \rightarrow B$ 这个顺序其实是深度优先后序遍历的顺序。

但是这个深度优先后序遍历指的是以联通分量作为节点进行的遍历，如果我们从任意一个节点做深度优先后序遍历是得不到这个顺序的。例如我们从联通分量中的节点 $D$ 开始遍历，接着来到了联通分量 $C$，虽然遍历完联通分量 $C$ 中所有节点之前肯定需要遍历完联通分量 $E$，但是不能保证所有 $E$ 中的节点都在 $C$ 之前被遍历，即可能有这样的顺序 $C_1 \rightarrow E \rightarrow C_2 \rightarrow \cdots$，这样的顺序是我们不想要的，因为我们必须从联通分量 $E$ 中的节点开始遍历。

虽然上面的深度优先遍历不能严格按照 $E \rightarrow C \rightarrow A \rightarrow D \rightarrow B$ 的顺序遍历，但是我们发现一定有分量 $C$ 中的节点在分量 $E$ 遍历完之后遍历的 $C_1 \rightarrow E \rightarrow C_2 \rightarrow \cdots$，例如 $C_2$ 在遍历完 $E$ 之后被遍历了，这给了我们灵感，如果我们取个逆，就可以得到一定有 $C$ 中的节点在 $E$ 分量节点被遍历之前遍历。

而我们想要的是一定要 $E$ 中的节点在 $C$ 中的节点被遍历之前遍历，怎么办，我们将整个图的方向改变一下，原来是 $a \rightarrow b$，现在变为 $b \rightarrow a$

然后进行深度优先后序遍历，然后取个逆就可以保证一定有在 $E$ 中的节点在 $C$ 中的节点遍历之前被遍历到，同理可以得到一定有 $C$ 中的节点在 $D$ 中的节点被遍历之前被遍历到，这就达到我们的目的，我们再根据这个顺序做 DFS 就可以统计出联通分量的个数了。

上面这个算法就是 Kosaraju 算法，总结上面的步骤如下：

• 图翻转得到反图
• 对反图做深度优先后序遍历，然后对遍历结果取逆
• 根据取逆后的结果依次做 DFS，统计联通分量个数

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

public class StrongCC {
    private DirectedGraph graph;
    private int[] visited;
    private int scccount;

    public StrongCC(DirectedGraph graph) {
        this.graph = graph;
        this.visited = new int[graph.V()];
        Arrays.fill(visited, -1);
        this.scccount = 0;

        // 翻转图
        TreeSet<Integer>[] reverse = new TreeSet[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            reverse[i] = new TreeSet<>();
        }
        for (int v = 0; v < graph.V(); v++) {
            for (int w: graph.adj(v)) {
                reverse[w].add(v);
            }
        }
        // 对翻转图做 DFS
        DFSDirectedGraph dfsDirectedGraph = new DFSDirectedGraph(new DirectedGraph(reverse));

        // 对深度优先后序遍历取逆
        ArrayList<Integer> res = dfsDirectedGraph.post();
        Collections.reverse(res);

        // 依次做 DFS，每做一次 DFS，联通分量个数增加
        for(int v: res) {
            if (visited[v] == -1) {
                dfs(v, scccount);
                scccount++;
            }
        }
    }

    private void dfs(int v, int id) {
        visited[v] = id;
        for (int w: graph.adj(v)) {
            if (visited[w] == -1) {
                dfs(w, id);
            }
        }
    }

    public ArrayList<Integer>[] components() {
        ArrayList<Integer>[] results = new ArrayList[scccount];

        for (int i = 0; i< scccount; i++) {
            results[i] = new ArrayList<>();
        }

        for (int v = 0; v < graph.V(); v++) {
            results[visited[v]].add(v);
        }
        return results;
    }
}