题解 | #检测循环依赖#

检测循环依赖

http://www.nowcoder.com/practice/8dc02ad98553432a90affc3a0484910b

题意整理

给定n门课程，这n门课程中存在一定的依赖关系，例如想要完成B课程，必须先完成A课程。依赖关系存储在一个数组里。
找出可以完成所有课程的一个顺序列表，如果不能完成所有课程，返回一个空数组。

方法一（深度优先搜索）

1.解题思路

新建一个邻接表，记录所有课程对应的后置课程。新建一个visited数组，用于记录课程状态。0表示未访问，1表示已访问，2表示已完成。另外定义一个变量valid，判断是否存在循环依赖。
然后遍历所有课程，进行深度优先搜索。每次将当前课程标记为已访问，如果当前后置课程未访问，继续搜索，如果存在循环依赖，直接返回。
每完成一次搜索，标记为已完成。已完成的一定是递归的最后一层，对应课程顺序的最后一门。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型二维数组 
     * @param n int整型 
     * @return int整型一维数组
     */
    
    //邻接表
    List<List<Integer>> graph;
    //判断是否存在循环依赖
    boolean valid=true;
    //记录课程状态，0表示未访问，1表示已访问，2表示已完成
    int[] visited;
    //记录可行的课程顺序
    int[] res;
    //res数组的游标
    int id;
    
    public int[] findOrder (int[][] prerequisites, int n) {
        //新建邻接表
        graph=new ArrayList<>();
        //初始化邻接表
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int[] cur:prerequisites){
            //给对应邻接表添加后置课程
            graph.get(cur[1]).add(cur[0]);
        }
        visited=new int[n];
        res=new int[n];
        id=n-1;
        
        //遍历所有课程，进行深度优先搜索
        for(int i=0;i<n&&valid;i++){
            if(visited[i]==0){
                dfs(i);
            }
        }
        return valid?res:new int[0];
    }
    
    private void dfs(int i){
        //标记为已访问
        visited[i]=1;
        for(int j:graph.get(i)){
            //如果当前后置课程未访问，继续搜索
            if(visited[j]==0){
                dfs(j);
            }
            //存在循环依赖
            else if(visited[i]==1){
                valid=false;
                return;
            }
        }
        //标记为已完成
        visited[i]=2;
        //已完成的一定是递归的最后一层，对应课程顺序的最后一门
        res[id--]=i;
    }
}

3.复杂度分析

时间复杂度：假设课程总个数为n，所有后置课程数为m，需要利用深度优先搜索访问所有课程，以及后置课程，所以时间复杂度是 $O (n + m)$ 。
空间复杂度：需要额外大小为m的邻接表存储后置课程，大小为n的递归栈，以及大小为n的visited数组记录课程状态，所以空间复杂度为 $O (n + m)$ 。

方法二（广度优先搜索+拓扑排序）

1.解题思路

新建一个邻接表，记录所有课程对应的后置课程。新建一个indegree数组，用于记录课程的入度。
遍历prerequisites数组，给邻接表和入度数组赋值。
然后新建一个队列，为后续搜索做准备。遍历所有课程，如果入度为0，则加入到队列。如果队列为空，说明有循环依赖，直接返回空数组。
进行广度优先搜索，取出当前课程，遍历所有后置课程，对应入度减1，如果入度变为0，则加入到队列。如果没访问完所有课程，而队列为空，说明存在环。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型二维数组 
     * @param n int整型 
     * @return int整型一维数组
     */
    public int[] findOrder (int[][] prerequisites, int n) {
        //邻接表
        List<List<Integer>> graph=new ArrayList<>();
        //入度数组
        int[] indegree=new int[n];
        //初始化邻接表
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int[] cur:prerequisites){
            //给对应邻接表添加后置课程
            graph.get(cur[1]).add(cur[0]);
            //入度加1
            indegree[cur[0]]++;
        }
        
        LinkedList<Integer> queue=new LinkedList<>();
        //将所有入度为0的课程加入到队列
        for(int i=0;i<n;i++){
            if(indegree[i]==0){
                queue.offer(i);
            }
        }
        //如果队列为空，说明有循环依赖，直接返回空数组
        if(queue.size()==0) return new int[0];
        
        int[] res=new int[n];
        int id=0;
        while(!queue.isEmpty()){
            //取出当前课程
            int i=queue.poll();
            res[id++]=i;
            for(int j:graph.get(i)){
                //后置课程入度减一
                indegree[j]--;
                //入度为0的课程入队
                if(indegree[j]==0){
                    queue.offer(j);
                }
            }
            //如果没访问完所有课程，而队列为空，说明存在环
            if(id<n&&queue.isEmpty()){
                return new int[0];
            }
        }
        return res;
    }
}