Java数据结构之有向图

术语

有向完全图：把所有顶点都用边连起来的图，共n(n-1)条边。
简单有向路径：不含重复顶点。我们讨论的“路径”都是简单的。
简单有向环：除了起终点之外不含重复顶点和边的环。
邻接表中的索引是边的起点，值是边的终点。
构造图

基本和无向图相同，其中邻接表存储边的时候只需要存储一次，而addEdge(int v,int w)参数有前后之分，前一个表示起点，后一个为终点。

/**
 * @Author haien
 * @Description Direct graph有向图
 * @Date 2018/12/4
 **/
public class Digraph {
    //顶点数
    private  int V;
    //边数
    private int E;
    //邻接点背包数组
    private Bag<Integer>[] adj;

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

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

    public int E(){
        return E;
    }

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

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

    /**
     * @Author haien
     * @Description 将图中所有边的方向逆转 
     * @Date 2018/12/4
     * @Param []
     * @return void
     **/
    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;
    }
}

深度优先搜索

和无向图几乎一样；能够判断从给定的一个点或一组点能到达哪些其他点，即单点可达性和多点可达性。

public class DirectedDFS {
    private boolean[] marked;

    /**
     * @Author haien
     * @Description 单点可达性：从一个点出发能到达哪些点
     * @Date 2018/12/4
     * @Param [G, s]
     **/
    public DirectedDFS(Digraph G,int s) {
        marked=new boolean[G.V()];
        dfs(G,s);
    }

    /**
     * @Author haien
     * @Description 多点可达性：从一组点中任一点触发能到达哪些点
     * @Date 11:24 2018/12/4
     * @Param [G, sources]
     **/
    public DirectedDFS(Digraph G,Iterable<Integer> 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];
    }
}

多点可达性的一个应用是在内存管理系统中，一个顶点表示一个对象，一条边则表示一个对象对另一个对象的引用。内存管理系统会周期性地回收不可达的对象。
拓扑排序
规定一条路径中起点到终点的优先级依次递减，用这种方法实现的排序叫拓扑排序。

拓扑排序中不可能存在环，因为环中的顶点根本无法分清优先级。

/**
 * @Author haien
 * @Description 寻找图中的有向环
 * @Date 2018/12/4
 **/
public class DirectedCycle {
    private boolean[] marked;
    //索引的上一个顶点
    private int[] lastVertex;
    //有向环中的所有顶点
    private Stack<Integer> cycle;
    //递归调用的栈上的所有顶点
    private boolean[] onStack;

    public DirectedCycle(Digraph G) {
        onStack=new boolean[G.V()];
        lastVertex=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(hasCycle()) return;
            else if(!marked[w]){
                lastVertex[w]=v;
                dfs(G,w);
            }
            else if(onStack[w]){
                cycle=new Stack<Integer>();
                for(int x=v;x!=w;x=lastVertex[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
        //递归出栈后，刚找到的环all元素全变成false，直到遇到还有其他邻接点可遍历的顶点，才保持true
        onStack[v]=false;
    }

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

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

然后我们来尝试几种排序方法，从中摸索哪一种符合拓扑排序

/**
 * @Author haien
 * @Description 基于深搜的顶点排序
 * @Date 2018/12/5
 **/
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);

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

详细过程参考《算法》579页reversePost过程，这就是拓扑排序了
拓扑排序的前提是不存在环，因此实现算法之前必须先检测环

Java数据结构之有向图

术语

构造图

深度优先搜索

拓扑排序

谢谢大爷~