2019-05-23拓扑排序

package 图;

public class Code_拓扑排序 { // 有向无环图
    static String[] v = {"a", "b", "c", "d", "e"};
    static int[][] graph = {
            {0, 0, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0}
    };
    static int n = graph.length;
    static int[] vis = new int[n];   // 查看是否被访问过
    static int[] topo = new int[n];
    static int t= n;
    public static void main(String[] args) {
        for(int i = 0; i < n; i++) {
            if(vis[i] == 1) {  
                // 如果这个点被标记成了1也就是这个点已经排好序了图中任何点都不能访问到它了
                continue;
            }
            boolean bool = dfs(i); 
            // 检验这个图是可以进行拓扑排序其实就是检验有没有回路的问题
            //如果只是单纯的排个序dfs直接给void就可以了
            if(!bool) {
                System.out.println(false);
                return;
            }
        }
        for(int i = 0; i < n; i++) {
            System.out.println(v[topo[i]]); // 输出排序
        }
    }
    public static boolean dfs(int i) {
        vis[i] = -1;
        /*
         * 这里的vis[i]标记成-1是为了检验在这个图中有没有回路配合后面的graph[i][j]监测
         * 检验的原理就是你这个点一进入递归我就把你标记成-1然后进行深搜其他点进来也标记成-1
         * 它们都存在栈中但是如果图中存在环的话也就是有一个点入栈了两次因为这个点没有出栈所以在
         * vis中是-1可以直接return false
         * 
         * */
        for(int j = 0; j < n; j++) {
            if(graph[i][j] > 0) {    // 检验是否有环路当前顶点i和j是否有指向也就是有没有路径
                if(vis[j] < 0) {
                    return false;
                }
                if(vis[j] == 0 && dfs(j) == false) {
                    return false;
                }
            }
        }
        topo[--t] = i; // 
        vis[i] = 1;  // 标记i节点已经走过了出度为0
        return true;
    }
    
}