#Java #BFS #Topological-sorting


  • 0

    This is a typical BFS topological sorting answer. Other than the algorithm, I'm much more interested in the Java representation of a graph. Should we use a int[][]/boolean[][], List<Set<Integer>>, Set<Integer>[] to represent a graph?

    • int[][]/boolean[][] is a workable idea, but it wastes some memory
    • List<Set<Integer>> or List<List<Integer>> seems to be a good alternative, but it's painful to check the validity of the index every time.
    • Set<Integer>[] is a nice workaround as long as we remember it's not allowed to put the parameterized type in the array constructor.

    boolean[][] graph

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            boolean[][] graph = new boolean[numCourses][numCourses];
            int[] indegree = new int[numCourses];
    
            // make a graph && indegree array
            for(int r=0; r<prerequisites.length; ++r) {
                int nextV = prerequisites[r][0];
                int v = prerequisites[r][1];
                graph[v][nextV] = true;
                indegree[nextV]++;
            }
    
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            for(int i=0; i<indegree.length; i++) {
                if(indegree[i] == 0) queue.offer(i);
            }
    
            if (queue.isEmpty()) return false;
            int count = 0;
    
            while(!queue.isEmpty()) {
                count ++;
                Integer v = queue.poll();
                indegree[v] = -1;
                for(int nextV=0; nextV<numCourses; ++nextV) {
                    if (graph[v][nextV]) {
                        if (indegree[nextV] == -1) return false;
                        indegree[nextV]--;
                        if (indegree[nextV] == 0) queue.offer(nextV);
                    }
                }
            }
            return count == numCourses;
        }
    

    Set<Integer>[]

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Set<Integer>[] graph = new Set[numCourses];
            int[] indegree = new int[numCourses];
    
            // make a graph && indegree array
            for(int r=0; r<prerequisites.length; ++r) {
                int nextV = prerequisites[r][0];
                int v = prerequisites[r][1];
                if (graph[v] == null) graph[v] = new HashSet<>();
                graph[v].add(nextV);
                indegree[nextV]++;
            }
    
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            for(int i=0; i<indegree.length; i++) {
                if(indegree[i] == 0) queue.offer(i);
            }
    
            if (queue.isEmpty()) return false;
            int count = 0;
    
            while(!queue.isEmpty()) {
                count ++;
                Integer v = queue.poll();
                indegree[v] = -1;
    
                if (graph[v] != null) {
                    for (int nextV : graph[v]) {
                        if (--indegree[nextV] == 0) queue.offer(nextV);
                    }
                }
            }
            return count == numCourses;
        }
    

Log in to reply
 

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