Basic Code Snippet for "Topological Sort(Kahn Algorithm)" in java.
Mihir_Mehta
202
SortingCareerTopological Sort

Problem statement -

  1. You are a college student and you want to study some advance course.
  2. But for studying advance course, you must know/study basic course for the same subject.
  3. Now arrange the courses in the order such that the student need not worry about choosing which course to study first, which course to choose next and so-on

Example -> numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
prerequisites[i,j] -> means in order to take course i, student must study course j first.

output of above case -> [0,2,1,3]

One of the possible solutions here is to apply "Kahn Algorithm" and return the "Topological Sorting".

class Solution {

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // topological sorting / kahn algorithm for scheduling courses
    int[] topologicalSort= new int[numCourses];
    int[] indegree= new int[numCourses];
    Map<Integer,List<Integer> > adjList= new HashMap<Integer, List<Integer> >();
    
    // create adjList / graph from 2D array "prerequisites"
    for(int i=0;i<prerequisites.length;i++){
        int des=prerequisites[i][0];
        int src=prerequisites[i][1];
        List<Integer> l= adjList.getOrDefault(src,new ArrayList<>());
        l.add(des);
        adjList.put(src,l);
        
        // add the in-degree
        indegree[des]++;   // in degree represents direction from src(prerequite course) to des(actual course)
    }
    
    // queue contains all nodes with degree 0
    Queue<Integer> q=new LinkedList<>();
    for(int i=0;i<numCourses;i++){
        if(indegree[i] == 0){
            q.add(i);
        }
    }
    
   int i=0;
   while(!q.isEmpty()){
       int node=q.remove();
       topologicalSort[i++]=node;
    
       // reduce the in degrees of the node's neighbors by 1
       if(adjList.containsKey(node)){
           for(Integer neighnor: adjList.get(node)){
               indegree[neighnor]--;
               
              if(indegree[neighnor] == 0){
                  q.add(neighnor);
              }
           }
       }   
   } 
    if(i == numCourses){
        return topologicalSort;  // return the ordering of courses array
    }
    
    return new int[0];  // case where ordering of courses can't be done i.e return empty array
}

}

Comments (0)