My DFS & BFS Java Solution


  • 0
    H
    public class Solution {
    // bfs solution
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        }
        
        boolean[] isVisited = new boolean[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        Map<Integer, Integer> inDegree = new HashMap<Integer, Integer>();
        
        constructGraph(numCourses, prerequisites, graph, inDegree);
        
        Queue<Integer> q = new LinkedList<Integer>();
        
        for (int i = 0; i < numCourses; i++) {
            if (!inDegree.containsKey(i)) {
                q.offer(i);
                isVisited[i] = true;
            }
        }
        
        while (!q.isEmpty()) {
            int tmp = q.poll();
            isVisited[tmp] = true;
            List<Integer> neighbors = graph.get(tmp);
            for (int next : neighbors) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) {
                    q.offer(next);
                }
            }
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (!isVisited[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    private void constructGraph(int numCourses, int[][] prerequisites, 
                                    Map<Integer, List<Integer>> graph, Map<Integer, Integer> inDegree) {
        for (int i = 0; i < numCourses; i++) {
            List<Integer> list = new ArrayList<Integer>();
            graph.put(i, list);
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            int end = prerequisites[i][1];
            if (inDegree.containsKey(end)) {
                inDegree.put(end, inDegree.get(end) + 1);
            } else {
                inDegree.put(end, 1);
            }
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            int key = prerequisites[i][0];
            int neighbor = prerequisites[i][1];
            graph.get(key).add(neighbor);
        }
    }}
    
    
    public class Solution {
    // dfs solution
    // status
    private static int UNVISITED = 0;
    private static int VISITED = 1;
    private static int PASSED = 2;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        } 
        
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        int[] status = new int[numCourses];
        Arrays.fill(status, UNVISITED);
        
        constructGraph(numCourses, prerequisites, graph);
        
        while (!isFinished(numCourses, status)) {
            int start = 0;
            for (int i = 0; i < numCourses; i++) {
                if (status[i] == UNVISITED) {
                    start = i;
                }
            }
            if (!dfs(graph, status, start)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean dfs(Map<Integer, List<Integer>> graph, int[] status, int start) {
        if (status[start] == VISITED) {
            return true;
        }
        
        // a loop in graph
        if (status[start] == PASSED) {
            return false;
        }
        
        status[start] = PASSED;
        List<Integer> nextList = graph.get(start);
        for (int next : nextList) {
            if (!dfs(graph, status, next)) {
                return false;
            }
        }
        status[start] = VISITED;
        return true;
    }
    
    private boolean isFinished(int numCourses, int[] status) {
        for (int i = 0; i < numCourses; i++) {
            if (status[i] == UNVISITED) {
                return false;
            }
        }
        return true;
    }
    
    private void constructGraph(int numCourses, int[][] prerequisites, Map<Integer, List<Integer>> graph) {
        for (int i = 0; i < numCourses; i++) {
            List<Integer> list = new ArrayList<Integer>();
            graph.put(i, list);
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            int key = prerequisites[i][0];
            int neighbor = prerequisites[i][1];
            graph.get(key).add(neighbor);
        }
    }}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.