4-2 Directed Graphs

总览（Glossary）

————————————————————————

一个有向图（directed graph, or simply digraph）是若干节点和有向边的集合。每条有向边有序地连接着一对节点。

————————————————————————

我们称一条有向边由节点对的第一个节点指向第二个节点。

关于有向图的概念和定义

出度（outdegree）：从一个节点出发的有向边的数量称为这个节点的出度
入度（indegree）：以一个节点结束的有向边的数量称为这个节点的入度
有向图中的任意两个节点之间有下面四种关系：没有边，有一条 v->w 边，有一条 w->v 边，有两条边 v->w 和 w->v
有向路径（directed path）：一个节点序列，其中每个节点（除最后一个）有一条边出发并指向序列中的下一个节点
有向环（directed cycle）：一条有向路径，其中至少有一条边连接的两个节点是相同的
简单环（simple cycle）：一个有向环，其中没有重复的节点或边（除了必须的首尾节点）
路径或环长度（length）：路径上有向边的条数
可到达（reachable）：如果有一条从 v 到 w 的有向路径，那么就说从 v 到 w 是可到达的。另外，我们接受这样的惯例：一个节点到它自己是可到达的。

有向图数据类型（Digraph data type）

API

    public class  Digraph
                  Digraph(int V)               // create a V-vertex digraph with no edges
                  Digraph(In in)               // read a digraph from input stream in
              int V()                          // number of vertices
              int E()                          // number of edges
             void addEdge(int v, int w)        // add edge v->w to this digraph
Iterable<Integer> adj(int v)                   // vertices connected to v by edges
          Digraph reverse()                    // reverse of this digraph
           String toString()                   // string representation

倒置有向图（Reverse a digraph）

将有向图中所有边反向，所有节点保持不变，返回一个新的有向图

public Digraph reverse()
{
    Digraph R = new Digraph(V);
    for (int v = 0; v < V; v++)
        R.addEdge(w, v);
    return R;
}

有向图中的可到达性（Reachability in digraph）

单源可到达问题：给定一个有向图和一个源节点 s，有没有一条从 s 出发的有向路径可以到达给定的目标节点 v
多源可到达问题：给定一个图和一个节点的集合，有没有一条从集合中任一节点出发的路径可以到达给定的目标节点 v

我们采用 DFS 来进行可到达性的判断

public class DirectedDFS
{
    private boolean[] marked;

    public DirectedDFS(Digraph G, int s)
    {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    public DirectedDFS(Digraph G, Iterable<Integer> sources)
    {
        marked = new boolean[G.V()];
        for (int s : G.adj(v))
            if (!makred[s]) dfs(G, s);
    }

    private void dfs(Digraph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }
}

————————————————————————

在一个有向图中，DFS 标记了所有从源节点的集合出发可到达的节点，所用时间与所有被标记节点的出度之和成正比。

————————————————————————

“标记-清理”的垃圾回收机制（Mark-and-sweep garbage collection）

多源可到达问题的一个重要应用就是在内存管理系统中。每个节点代表一个对象(object)，每条边代表一个引用(reference)。在程序的执行过程中，一部分对象可以直接存取（directly accessible），它们对应着源节点的集合；另一部分对象只能通过引用访问，它们对应着目标节点。垃圾回收机制定期从直接存取对象出发，扫描整个内存空间，利用DFS，标记出所有可以访问到的对象。然后，把那些不能访问到的对象占用的内存空间释放。

寻找路径

和无向图类似（DFS和BFS，即单源路径和单源最短路径）

环和DAG（Cycles and DAGs）

判定一个有向图中是否含有环是一个比较复杂的问题，下面先从规划安排这个具体的问题出发。

规划安排问题（Scheduling problems）

广义的规划安排问题指的是通过安排，使得在若干限制条件下，若干任务可以完成。这里的限制条件可以是任务所需要的时间，也可以是任务所需要的资源等。一个常见且重要的限制条件就是次序，即任务之间的次序必须满足一定条件。

次序安排问题（Precedence-constrained scheduled）

给定若干需要完成的任务，与若干条次序限制，即某个任务必须在另外一个任务完成之后开始，我们应该怎么安排任务的顺序，使得所有任务都能完成，且不违背任意一条次序限制条件。

可以用节点来表示任务，用有向边表示任务之间的顺序限制，如上图所示。例如，任务1必须在任务0之后完成。这样，次序安排问题就等价于更基本的一个问题，称为拓扑排序。

给定一个有向图，将所有节点按如下规则排序：任意有向边都由一个排在前面的节点出发，指向一个排在后面的节点。（或者报告这样的排序不可能实现）。上面的有向图经过拓扑排序后如下图所示：

环的检测（Cycles detection）

设想这样的顺序限制：x 必须在 y 之前完成，y 必须在 z 之前完成，z 必须在 x 之前完成。这样的话，就不存在符合条件的安排了。换言之，如果一个有向图含有环，那么它就不能进行拓扑排序。

一个有向图可能有指数级数量个环，我们只需要找出其中一个，而不是全部。

————————————————————————

一个有向无环图（directed acyclic graph, as DAG）是一个不含环的有向图。

————————————————————————

我们使用深度优先来实现环的检测，在每次递归调用中，我们用一个栈来表示当前的路径（通过在调用前将元素对应的位置标为True，调用后将元素对应位置标为False）。如果我们找到了一条路径 v-w 而 w 恰好在栈里，那么就说明存在一个环，因为 w 在栈里隐含了有一条路径 w-v 。

public class DirectedCycle
{
    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle;
    private boolean[] onStack;

    public DirectedCycle(Digraph G)
    {
        onStack = new boolean[G.V()];
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }

    private void dfs(Digraph G, int v)
    {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj(v))
            if (this.hasCycle())    return;
            else if (!marked[w])
            {    edgeTo[w] = v; dfs(G, w);    }
            else if (onStack[w])
            {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        onStack[v] = false;
    }

    public boolean hasCycle()
    {    return cycle != null;    }

    public Iterable<Integer> cycle()
    {    return cycle;    }
}

下面是一个例子

拓扑排序（Topological sort）

————————————————————————

一个有向图可以进行拓扑排序当且仅当它是一个DAG

————————————————————————

运用DFS，我们可以有三种可行顺序来遍历整个DAG（取决于使用的数据结构和在递归调用之前/后存储结点），分别是：

先序（Preorder）：在递归调用之前将节点添加到队列中
后序（Postorder）：在递归调用之后将节点添加到队列中

倒置后序（Reverse postorder）：在递归调用之后将节点添加到栈中

public class DepthFirstOrder
{
    private boolean[] marked;

    private Queue<Integer> pre;
    private Queue<Integer> post;
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph G)
    {
        pre  = new Queue<Integer>();
        post = new Queue<Integer>();
        reversePost = new Stack<Integer>();
        marked = new boolean[G.V()];

        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }

    private void dfs(Digraph G, int v)
    {
        pre.enqueue(v);            // before the recursive call

        marked[v] = true;
        for ( int w: G.adj(v))
            if (!marked[v])
                dfs(G, w);

        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre()
    {    return pre; }
    public Iterable<Integer> post()
    {    return post; }
    public Iterable<Integer> reversePost()
    {    return reversePost; }
}

下面是详细的图解

————————————————————————

一个DAG的倒置后序遍历也是它的一种拓扑排序结果

————————————————————————

证明：
考虑任意一条边v-w，当调用dfs(v)的时候，必然有以下三种情况之一：

dfs(w)被调用了(called)，而且也已经调用完成(returned)，意味着w已经被标记了。

dfs(w)还未被调用了(called)，意味着w还未被标记，所以dfs(v)将会导致dfs(w)，那么，dfs(w)一定在dfs(v)之前调用完成。

dfs(w)被调用了(called)，但还未调用完成，这暗示了有一条w-v的路径，那么这个图就不是DAG，所以这种情况是不可能的。
对于上面两种可能的情况，dfs(w)都在dfs(v)之前调用完成，所以在后序顺序中，w出现在前面；在倒置后序顺序中，w出现在v的后面。这样，在倒置后序顺序中，就满足了我们需要的每条边v-w都是从一个排在前面的节点指向排在后面的节点。

————————————————————————

利用DFS，我们可以在$O(V+E)$时间内对一个DAG进行拓扑排序。（利用一次DFS探测有向图是否含有环，利用另一次DFS进行倒置后序排序）

————————————————————————

有向图的强连通性（Strong connectivity in digraphs）

————————————————————————

如果两个节点v和w互相可到达，我们就说这两个节点是强连通的(strongly connnected)；如果一个有向图中任一节点与其他所有节点都是强连通的，那么我们说这个有向图是强连通的

————————————————————————

强连通具有以下性质：

自反性（Reflexive）：每个节点和它自己是强连通的
对称性（Symmetric）：如果v与w是强连通的，那么w与v就是强连通的
传递性（Transitive）：如果v与w是强连通的，w和x是强连通的，那么v与x也是强连通的

强连通部分（Strong components）

类似于无向图中的连通部分概念，有向图可以分为若干个强连通部分，如下图所示

一个含有V个节点的有向图有 1 ~ V 个强连通部分：当它是强连通图时有1个连通部分，当它是DAG时有V个连通部分

实际应用

强连通性是有向图的一个重要的特性，有以下方面的应用：

application	vertex	edge
web	page	hyperlink
textbook	topic	reference
software	module	call

API

public class SCC
            SCC(Digraph G)                         // 预处理构造函数
    boolean stronglyConnected(int v, int w)        // v 和 w 是强连通的吗？
        int count()                                // 强连通部分的数量

Kosaraju’s algorithm

利用这个算法，我们很快地将图分成若干个连通部分，算法步骤如下：

给定一个有向图G，用 DepthFirstOrder计算出它的倒置有向图G^R的倒置后序（reverse postorder）
对G用标准的DFS，但是在循环的时候，采用刚计算出来的顺序，而不是常规的数字顺序
在一次dfs调用中标记的节点都在同一个强连通部分中，所以可以给它们标上强连通部分的序号

程序如下：

public class KosarajuSCC
{
    private boolean[] marked;
    private int[] id;
    private int count;

    public KosarajuSCC(Digraph G)
    {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder order = new DepthFirstOrder(G.reverse());
        for (int s : order.reversePost())
            if (!marked[s])
            {    dfs(G, s); count++; }
    }

    private void dfs(Digraph G, int v)
    {  // same as standard dfs, omitted  }

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

    public int count()
    {    return count;    }
}

————————————————————————

在一个有向图G的DFS搜索中，如果未标记节点按照由G^R的倒置后序顺序逐一进行dfs调用，那么在构造函数中的一次dfs(G,s)调用中标记的节点都处于同一个强连通部分

————————————————————————

证明：
1. 先证明必要性，即每个与节点s强连通的节点v都会在构造函数中的dfs(G,s)调用中被标记。
利用反证法证明。假设有个节点v与s强连通，但却没有在dfs(G,s)调用中被标记。由于s有一条到v的路径，但v却未在dfs(G,s)调用中被标记，说明v在dfs(G,s)调用前就已经被标记了。又因为从v有一条到s的路径，且v在dfs(G,s)调用前就已经被标记了，所以在调用dfs(G,v)的过程中，一定会递归调用dfs(G,s)，则说明dfs(G,s)不会再构造函数中被调用。而前提是dfs(G,s)在构造函数中被调用，所以产生矛盾，故命题成立。
2. 再证明充分性，即每个在构造函数中的dfs(G,s)调用中标记的节点v都与s是强连通的。
由于v是在dfs(G,s)调用中被标记的，所以在G中从s到v一定有一条路径，故只要证明G中从v到s有一条路径即可，就能说明v和s是强连通的。这等价于要证明在G^R中有一条从s到v的路径。
由前提可知，在dfs(G,s)中标记了v，所以说明在倒置后序中，v排在s的后面。根据reversePost的构造过程可知，G^R中的dfs(G,v)一定比dfs(G,s)先调用完成。
那么在G^R的DFS调用中就有以下两种情况：
(1) dfs(G,v)比dfs(G,s)先调用
(2) dfs(G,v)比dfs(G,s)后调用
如下图所示

其中，如果是第一种情况是不可能的，因为在G^R中有一条从v到s的路径，所以只可能是第二种情况。在这种情况下，可以看出来在G^R中从s到v有一条路径，故证毕。

下图是算法的详细追踪

————————————————————————

Kosaraju 算法使用O(V+E)的时间和空间进行预处理，然后支持O(1)复杂度的强连通查询

————————————————————————

给定节点对的可到达查询（All-pairs reachability）

给定节点v和w，查询是否有一条v到w的路径。对于无向图来说，只需要查询v和w是不是属于同一个连通部分，但对于有向图来说，却不能通过查询v和w是不是属于同一个强连通部分来确定有没有这样的路径。

我们可以通过计算图G的传递闭包来进行查询。由于图的传递闭包是比较密的图，所以常用邻接矩阵来表示。可以利用DirectedDFS计算传递闭包，如下所示：

public class TransitiveClosure
{
    private DirectedDFS[] all;
    TransitiveClosure(Digraph G)
    {
        all = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++)
            all[v] = new DirectedDFS(G, v);
    }

    public boolean reachable(int v, int w)
    {    return all[v].marked(w);    }
}

不过这个方法只适用于比较小的图，因为它的空间复杂度为$O(V^2)$，时间复杂度为$O(V+E)$，能达到常数级的查询速度但却不需要平方级的空间的算法仍然还在研究中。