算法（第4版） Chapter 4.2 有向图

摘要：只好特地拎出来记录证明一下算法步骤第一步在逆图上运行，将顶点按照逆后序方式压入栈中显然，这个过程作用在有向无环图上得到的就是一个拓扑排序作用在非上得到的是一个伪拓扑排序第二步在原图上按第一步的编号顺序进行。等价于已知在逆图中存在有向路径。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 谢路云
Chapter 4 Section 2 有向图

修改了方法void addEdge(v, w) 添加的边为单向的， 从v到w

修改了方法adj(v) 返回的是从v指出去的边连接的顶点

增加了方法Digraph reverse() 创建了一个反向边的图副本，因为有时候我们需要的是指向特定顶点的其他顶点

public class Digraph {
    private final int V;
    private int E;
    private Bag[] adj;

    public Digraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag();
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

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

    public Iterable adj(int v) {
        return adj[v];
    }

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

增加了构造函数DirectedDFS(G,sources) 一个source生成一棵树，n个sources生成好n棵树；也有可能是一棵树，只是先找到了孙子，没法通过孙子找爸爸和爷爷，后来输入了爷爷，找到了爸爸，连到了孙子，形成了一棵大树。

基本和有向图没区别

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 sources) {
        marked = new boolean[G.V()];
        for (int s : sources)
            if (!marked[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);
    }

    public boolean marked(int v) {
        return marked[v];
    }
}

标记-清除的垃圾箱

寻路

调度问题

拓扑排序 给定一副有向图，将所有顶点排序，使得所有的有向边从排在前面的元素指向后面的元素

有向无环图 Directed Acyclic Graph （DAG）

方法boolean hasCycle() 有向环检测

public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private Stack cycle; // vertices on a cycle (if one exists)
    private boolean[] onStack; // vertices on recursive call stack

    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; //这个变量是神来之笔。因为有好几棵树，但我只要查我所在的这棵树。所以在递归的时候一路把这棵树标成true，在返回之前再标回false。为下一棵树可以循环再利用做准备。
        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();
                for (int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);//v压了两次，第一次作为箭头终点，第二次作为箭头起点
            }
        onStack[v] = false;
    }

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

    public Iterable cycle() {
        return cycle;
    }
}

前提

当且仅当一幅图是有向无环图时，才能进行拓扑排序

一种拓扑排序的实现方式

深度优先搜索DFS

顶点排列顺序

前序 递归调用之前将顶点加入队列

后续 递归调用之后将顶点加入队列

逆后续 递归调用之后将顶点压入栈

顶点排列顺序

就是记录顶点的位置和方式不一样

public class DepthFirstOrder {
    private boolean[] marked;
    private Queue pre; // vertices in preorder
    private Queue post; // vertices in postorder
    private Stack reversePost; // vertices in reverse postorder

    public DepthFirstOrder(Digraph G) {
        pre = new Queue();
        post = new Queue();
        reversePost = new Stack();
        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);
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable pre() {
        return pre;
    }

    public Iterable post() {
        return post;
    }

    public Iterable reversePost() {
        return reversePost;
    }
}

复杂度：

时间： V+E

（为什么我觉得Topological这个类没干什么实事，DirectedCycle检测是否是有向无环图，DepthFirstOrder进行了排序。。。Topological感觉就封装了一下）

public class Topological {
    private Iterable order; // topological order

    public Topological(Digraph G) {
        DirectedCycle cyclefinder = new DirectedCycle(G);
        if (!cyclefinder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost(); //排序方式
        }
    }

    public Iterable order() {
        return order;
    }

    public boolean isDAG() {
        return order == null;
    }
}

定义

w和v是相互可达的，则称它们为强连通的(Strongly Connected)
（v到w有一条路径，则w是从v可达的）

如果有向图G的每两个顶点都强连通，称G是一个强连通图。

有向图的极大强连通子图，称为强连通分量(Strongly Connected Components/Strong Components)

两个顶点是强连通的，当且仅当它们在同一个有向环中

性质

自反性

对称性

传递性

Strongly Connected Components

算法步骤很简单，但是原理很玄幻。。。只好特地拎出来记录+证明一下

第一步：在逆图G^R上运行DFS，将顶点按照逆后序（reversePost）方式压入栈Stack s中
（显然，这个过程作用在有向无环图DAG上得到的就是一个拓扑排序；作用在非DAG上得到的是一个伪拓扑排序）

第二步：在原图G上按第一步s.pop()的编号顺序进行DFS。
（栈的特点是FILO，先进后出）

算法基于CC(ConnectedComponents)

CC按顺序0~G.V()

SCC按顺序s.pop()

SCC顺序怎么得到？

类DepthFirstOrder

两次DFS

图示两次DFS

复杂度：所需时间与空间与V+E成正比，连通性查询为常数时间

时间： 处理有向图的反向图，+ 2次DFS 这三步所需的时间都与V+E成正比

空间： 反向复制一副有向图的空间与V+E成正比

连通性查询： 数组id[]查询，常数时间

public class KosarajuSCC {
    private boolean[] marked; // reached vertices
    private int[] id; // component identifiers
    private int count; // number of strong components

    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[w]) 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() { //复制书上的，感觉返回的不是强连通的个数N，因为从零开始计数，所以返回的是N-1
        return count;
    }
}

原图

pop顺序　　　→→→→　　　　　→→→→→→→→→
7 → 8　6 → 9 → 11　10 → 12　0 → 5 → 4 → 3 → 2　1
　←　　　　　←←←←←←　　　←←←←←←←　　　　　　

由于排版问题只画了部分的有向边

可见是否是环，应该从１开始排除，因为１是图中最深的结点，最有可能只有指向１的，而没有从１指出去的。通过开始一个一个排查，应该是一种比较好的想法。

证明的目标，就是最后一步 --- 每一颗搜索树代表的就是一个强连通分量

首先 最后一步是在原图G中通过s找到其他顶点v的，即从s→v是可达的。
那么我们需要证明，原图G中v→s也是可达的。

等价于已知：在逆图G^R中存在有向路径v→s。
那么要证明：逆图G^R中从s→v是可达的。

而之所以DFS(s)能够在DFS(v)之前被调用，是因为在对G获取ReversePost-Order序列时，s出现在v之前，这也就意味着，v是在s之前加入该序列的(因为该序列使用栈作为数据结构，先加入的反而会在序列的后面)。

因此根据DFS调用的递归性质，DFS(v)应该在DFS(s)之前返回，而有当时在逆图G^R中两种情形满足该条件：
DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END

第一种情形下，调用DFS(v)却没能在它返回前递归调用DFS(s)，与在逆图G^R中存在有向路径v→s相矛盾的，因此不可取。
故情形二为唯一符合逻辑的调用过程。而根据DFS(s) START -> DFS(v) START可以推导出在逆图G^R中存在有向路径s→v。

所以从s到v以及v到s都有路径可达，证明完毕。

顶点对的四种情况

w⇆v 强连通
w→v
w←v
w⇎v

问题：如何写一个算法判断从w到v是可达的吗？
有向图的可达性问题 和 连通性 有很大区别。 因为连通性是双向的，可达性是单向的。

目前的解决办法：传递闭包（其实就是一个类似于邻接矩阵的矩阵，用来记录是否连通）

给每个顶点创立了一棵树，在每棵树里有数组marked[V]，标记是否连通。

复杂度

空间：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);
    }
}