有向图（二）

拓扑排序：

public class Topological{
    private Iterable<Integer> order;        //顶点的拓扑排序
    public Topological(Digraph G){
        DirectedCycle cyclefinder = new DirectedCycle(G);
        if(!cyclefinder.hasCycle()){
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }
    public Iterable<Integer> order(){
        return order;
    }
    public boolean isDAG(){
        return order != null;
    }
    public static void main(String[] args){
        String filename = args[0];
        String separator = args[1];
        SymbolDigraph sg = new SymbolDigraph(filename, separator);
        Topological top = new Topological(sg.G());
        for( int v: top.order())
            StdOut.println(sg.name(v));
    }
}

一幅有向图的拓扑排序即为所有顶点的逆后序排列。
证明： 对于任意边v->w，在调用dfs(v)时，只会是以下两种情况：
1.dfs(w)已经被调用过且已经返回了（w已经被标记）。
2.dfs(w)还没有被调用（w还未被标记），因此v->w会直接或间接调用并返回dfs(w)，且dfs(w)会在dfs(v)返回之前返回。
在两种可能的情况中，dfs(w)都会在dfs(v)之前完成，因此在后序排列中w排在v之前而在逆后序排列中w排在v之后。因此任意一条边的v->w都如我们所愿地从排名较前的点指向排名较后的点。

有向图中的强连通性

如果两个顶点v和w是相互可达的，则称它们为强连通的。

强连通分量的API

public class SCC
             SCC(Digraph G)              //预处理构造函数
     boolean strongConnected(int v, int w)     //判断v和w是否连通
         int count()              //图中强连通分量总数
         int id(int v)              //v所在的强连通分量的标识符

计算无向图中的连通分量只是深度优先搜索的一个简单应用。Kosaraju算法简单的修改之前的算法即可实现新的功能。

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){
        marked[v] = true;
        id[v] = count;
        for(int w:G.adj(v))
            if( !marked[s])
                dfs(G, 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;
    }
}

先使用深度优先搜索查找给定的有向图G的反向图，根据由此得到的所有顶点的逆后序再次深度优先处理有向图（Kosaraju算法），其构造函数中的每一次递归调用所标记的顶点都在同一个强连通分量中。

---

顶点对的可达性
对于“是否存在一条从一个给定的顶点v到另一个给定的顶点w的路径”等类似的问题，在有向图中需要线性级别的预处理时间才能支持常数时间的查询操作。

有向图的传递闭包是由相同的一组顶点组成的另一幅有向图，在传递闭包中存在一条从v指向w的边当且仅当在G中w是从v可达的。

根据约定，每个顶点对于自己都是可达的，因此传递闭包会含有V个自环。一般而言，一幅有向图传递闭包所含的边都比原图多得多，一幅稀疏图的传递闭包确实一幅稠密图也是很常见的，例如含有v个顶点和v条边的有向环的传递闭包是一幅v²条边的有向完全图。因为传递闭包一般都很稠密，我们通常将它们表示为一个布尔值矩阵，其中v行w列的值为true当且仅当w是从v可达的。与其计算一幅有向图的传递闭包，比如使用深度优先搜索算法来实现以下API：

public class TransitiveClosure
             TransitiveClosure(Digraph G)         // 预处理的构造函数
     boolean reachable(int v, int w)              //判断w是否可从v到达

下面是实现的代码，无论对于稀疏还是稠密的图，它都是理想的解决方案。但它不适用于在实际应用中遇到的大型有向图，因为构造函数所需的空间和v²成正比，所需的时间和v(v+e)成正比。

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);
    }
    boolean reachable(int v, int w){
        return all[v].marked(w);
    }
}