Clean Java Solutions: BFS and DFS


  • 1
    Y

    1. BFS

    Refers to classic Kahn's Algorithm.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            
            // build the directed graph with adjacency list
            Map<Integer, Set<Integer>> outgoing = new HashMap<>();  // node ---> set of nodes
            Map<Integer, Set<Integer>> incoming = new HashMap<>();  // node <--- set of nodes
            for (int i = 0; i < numCourses; i++) {
                outgoing.put(i, new HashSet<>());
                incoming.put(i, new HashSet<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                outgoing.get(prerequisites[i][1]).add(prerequisites[i][0]);
                incoming.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
            
            /**
             * Kahn's Algorithm (BFS)
             */
            
            Queue<Integer> queue = new LinkedList<>();
            
            // add all nodes with no imcoming edge to the queue
            for (int i = 0; i < numCourses; i++) {
                if (incoming.get(i).isEmpty()) {
                    queue.offer(i);
                }
            }
            
            while (!queue.isEmpty()) {
                int course = queue.poll();
                for (int neighbor : outgoing.get(course)) {
                    // edge: course ---> neighbor
                    incoming.get(neighbor).remove(course);
                    if (incoming.get(neighbor).isEmpty()) {
                        queue.offer(neighbor);
                    }
                }
            }
            
            // if graph has edges, there is no topological ordering exists, return false
            for (int i = 0; i < numCourses; i++) {
                if (!incoming.get(i).isEmpty()) {
                    return false;
                }
            }
            
            return true;
        }
    }
    

    2. DFS

    Use a visited[] array:

    • visited[i] == 0 represents the course i has NOT been visited;
    • visited[i] == 1 represents the course i is being visited;
    • visited[i] == 2 represents the course i has been visited.

    The implementation is pretty straightforward.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            
            // build the directed graph with adjacency list
            Map<Integer, Set<Integer>> adjacencyList = new HashMap<>();  // node ---> set of nodes
            for (int i = 0; i < numCourses; i++) {
                adjacencyList.put(i, new HashSet<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                adjacencyList.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
            
            /**
             * Find Circle (DFS)
             */
            
            int[] visited = new int[numCourses];  // 0: unvisited; 1: being visited; 2: visited
            for (int i = 0; i < numCourses; i++) {
                if (visited[i] == 0 && !dfs(i, adjacencyList, visited)) {
                    return false;
                }
            }
            
            return true;
        }
        
        // detect circle (if a circle is detected, return false)
        private boolean dfs(int course, Map<Integer, Set<Integer>> adjacencyList, int[] visited) {
            
            visited[course] = 1;  // mark course as being visited
            for (int neighbor : adjacencyList.get(course)) {
                if (visited[neighbor] == 1) {  // circle detected
                    return false;
                }
                if (visited[neighbor] == 0 && !dfs(neighbor, adjacencyList, visited)) {  // circle detected
                    return false;
                }
            }
            visited[course] = 2;  // mark course as visited
            return true;
        }
    }
    

Log in to reply
 

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