Java数据结构中图的进阶详解

// 有向图
 
public class Digraph {
    // 记录顶点的数量
     
    private final int V;
 
    //记录边的数量
    private int E;
 
    //定义有向图的邻接表
    private Queue <Integer>[] adj;
 
    public Digraph (int v) {
        //初始化顶点数量
        this.V = v;
        //初始化边的数量
        this.E = 0;
        //初始化邻接表
        adj = new LinkedList[v];
        //初始化邻接表的空队列
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }
    public int V () {
        return V;
    }
    public int E () {
        return E;
    }
 
    //添加一条 v -> w的有向边
    public void addEage (int v , int w) {
        adj[v].add(w);
        ++E;
    }
 
    //获取顶点v 指向的 所有顶点
    public Queue<Integer> adj (int v) {
        return adj[v];
    }
 
    //将有向图 反转 后返回
    public Digraph reverse () {
        //创建一个反向图
        Digraph reverseDigraph = new Digraph(V);
        //获取原来有向图的每个结点
        for (int i = 0; i < V; i++) {
            //获取每个结点 邻接表的所有结点
            for (Integer w : adj[i]) {
                //反转图记录下 w -> v
                reverseDigraph.adj(w).add(i);
            }
        }
        return reverseDigraph;
    }
}
 

 
/**
 *  检查图中是否存在环
 */
public class DirectedCycle {
    /**
     * 索引代表顶点，用来记录顶点是否被搜索过
     */
    private boolean[] marked;
 
    /**
     * 判断图中是否有环
     */
    private boolean hasCycle;
 
    /**
     * 采用栈的思想，记录当前顶点是否已经存在 当前搜索的的路径上
     * 存在则可以判断 图中是存在环的
     */
    private boolean[] onStack;
 
    /**
     * 判断传入的有向图 是否存在环
     * @param G
     */
    public DirectedCycle (Digraph G) {
        marked = new boolean[G.V()];
        onStack = new boolean[G.V()];
        hasCycle = false;
        //因为不知道从那个点出发 可能存在环
        //所以需要从所有的顶点都出发搜索 判断是否存在环
        for (int i = 0; i < G.V(); i++) {
            dfs(G,i);
        }
    }
 
    /**
     * 采用深度搜索 判断有向图是否存在环
     * onStack 入栈出栈 然后判断当前搜索的顶点是否已经在搜索路径上
     *
     * @param G
     * @param v
     */
    private void dfs (Digraph G,int v) {
        //标记顶点已经搜索过
        marked[v] = true;
        for (Integer adj : G.adj(v)) {
            //判断v 是否已经在搜索的路径上了
            if(marked[adj] && onStack[adj]) {
                //存在环
                hasCycle = true;
            }else {
                //采用回溯的思路
                //让顶点入栈
                onStack[adj] = true;
                dfs(G,adj);
                //回溯 顶点出栈
                onStack[adj] = false;
            }
        }
    }
 
    /**
     * 判断是否存在环
     * @return
     */
    public boolean hasCycle(){
        return hasCycle;
    }
 
}

 
/**
 * 深度优先搜索 的顶点排序
 */
public class DepthFirstOrder {
    /**
     * 索引代表顶点 ，用来记录顶点是否已经被搜索过了
     */
    private boolean[] marked;
 
    /**
     * 使用栈记录深度优先搜索下的顶点
     */
    private Stack<Integer> reversePost;
 
    public DepthFirstOrder (Digraph G) {
        marked = new boolean[G.V()];
        reversePost = new Stack<>();
        for (int i = 0; i < G.V(); i++) {
            //如果顶点已经被搜索过则不用
            if(!marked[i])
                dfs(G,i);
        }
    }
 
    /**
     * 基于深度优先搜索，生成顶点线性序列
     * @param G
     * @param v
     */
    private void dfs (Digraph G, int v) {
        //标记顶点已经被搜索过
        marked[v] =  true;
        for (Integer w : G.adj(v)) {
            if(!marked[w])
                dfs(G,w);
        }
        //记录到线性序列中
        reversePost.push(v);
    }
 
    /**
     * 获取顶点线性序列
     * @return
     */
    private Stack<Integer> ReversePost() {
        return reversePost;
    }
}