Course Schedule

Solution Approach 

The base of the solution is to think of this problem as a graph problem where the tasks are the vertices, and the prerequisites are the edges. If task u is a prerequisite of task v; we’ll add a directed edge from u to v. 

Now, you must have noticed that this problem reduces to just finding the correct topological ordering of the vertices of the above-described graph. 

The basic approach is a topological sorting algorithm for a directed acyclic graph (DAG) using an adjacency list and indegree array. Where algorithm will add all vertices with zero indegree to a queue, processes each vertex by updating the indegree of its adjacent vertices, and adds them to the queue if their indegree becomes zero. The algorithm will continue until the queue is empty or all vertices have been processed. The output would be an array representing the order in which the vertices should be processed to satisfy all the prerequisites, or an empty array if there is a cycle in the graph.

Ok, before we proceed, what do you think is it possible to find topological ordering in cyclic graphs?

Consider the below cyclic graph and try to find the correct topological order.

Yes, you guessed it right. In cyclic graphs, you can't decide which one to choose first.

Thus cyclic graphs never have any topological ordering, so if the graph contains a cycle, we’ll return an empty array.

Algorithm

• Initialize adjacency list and indegree array based on the given input.
   
• Add all vertices with zero indegree to a queue.
   
• Process each vertex in the queue by updating the indegree of its adjacent vertices and adding them to the queue if their indegree becomes zero.
   
• Repeat step 3 until the queue is empty or all vertices have been processed.
   
• If count of processed vertices is less than the total number of vertices, return an empty array as there is a cycle in the graph.
   
• Otherwise, return the order of the vertices in the order they were processed.

Dry Run

We will discuss the dry run for the below case

• totalCourses = 6
• prerequisites = [{2,0}, {2,3}, {3,4}]

Below are the ordering steps

The correct order for the above case will be 0, 1, 4, 3, 2.

Java Implementation

import java.util.*;

public class GraphTopologicalSort {
   
    public int[] findOrder(int totalCourses, int[][] courseToReadBefore) {
        List<Integer>[] adjList = new ArrayList[totalCourses];
        int[] indegree = new int[totalCourses];

        // Initialize adjacency list and indegree array
        for(int i=0; i<totalCourses; i++){
            adjList[i] = new ArrayList<Integer>();
        }

        // Populate adjacency list and indegree array
        for(int i=0; i<courseToReadBefore.length; i++){
            int u = courseToReadBefore[i][0];
            int v = courseToReadBefore[i][1];
            adjList[v].add(u);
            indegree[u]++;
        }

        Queue<Integer> q = new LinkedList<>();

        // Add all vertices with zero indegree to queue
        int i = 0;
        while(i < totalCourses){
            if(indegree[i] == 0){
                q.add(i);
            }
            i++;
        }

        int[] order = new int[totalCourses];
        int count = 0;

        // Process vertices in queue
        while(!q.isEmpty()){
            int curr = q.poll();
            order[count++] = curr;
            int j = 0;
            while(j < adjList[curr].size()){
                int next = adjList[curr].get(j);
                indegree[next]--;
                if(indegree[next] == 0){
                    q.add(next);
                }
                j++;
            }
        }

        // If the count is less than the total courses, there is a cycle in the graph
        if(count < totalCourses){
            return new int[]{};
        }
       
        return order;
    }

    public static void main(String[] args) {
        int totalCourses = 5;
        int[][] prerequisites = {{2,0}, {2,3}, {3,4}};
        GraphTopologicalSort graphTopoSort = new GraphTopologicalSort();
        int[] order = graphTopoSort.findOrder(totalCourses, prerequisites);
        if(order.length == 0){
            System.out.println("It is impossible to finish all the tasks.");
        } else {
            System.out.print("The order to read the courses is: ");
            for(int i=0; i<order.length; i++){
                System.out.print(order[i] + " ");
            }
        }
    }
}

Output

C++ Implementation

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class GraphTopologicalSort {
public:
    vector<int> findOrder(int totalCourses, vector<vector<int>>& courseToReadBefore) {
        vector<vector<int>> adjList(totalCourses);
        vector<int> indegree(totalCourses, 0);

        // Initialize adjacency list and indegree array
        for(int i=0; i<totalCourses; i++){
            adjList[i] = vector<int>();
        }

        // Populate adjacency list and indegree array
        for(int i=0; i<courseToReadBefore.size(); i++){
            int u = courseToReadBefore[i][0];
            int v = courseToReadBefore[i][1];
            adjList[v].push_back(u);
            indegree[u]++;
        }

        queue<int> q;

        // Add all vertices with zero indegree to queue
        int i = 0;
        while(i < totalCourses){
            if(indegree[i] == 0){
                q.push(i);
            }
            i++;
        }

        vector<int> order(totalCourses, 0);
        int count = 0;

        // Process vertices in queue
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            order[count++] = curr;
            for(int j=0; j<adjList[curr].size(); j++){
                int next = adjList[curr][j];
                indegree[next]--;
                if(indegree[next] == 0){
                    q.push(next);
                }
            }
        }

        // If the count is less than the total courses, there is a cycle in the graph
        if(count < totalCourses){
            return vector<int>();
        }
        return order;
    }
};

int main() {
    int totalCourses = 5;
    vector<vector<int>> prerequisites = {{2,0}, {2,3}, {3,4}};
    GraphTopologicalSort graphTopoSort;
    vector<int> order = graphTopoSort.findOrder(totalCourses, prerequisites);
    if(order.size() == 0){
        cout << "It is impossible to finish all the tasks." << endl;
    } else {
        cout << "The order to read the courses is: ";
        for(int i=0; i<order.size(); i++){
            cout << order[i] << " ";
        }
    }
    return 0;
}

Output

Complexities

Time complexity

O(V+E), where V is the number of vertices and E is the number of edges.

Reason: Because there is a for loop running V times and inside it, there is a loop running for edges, and the total number of edges is E.

Space complexity

O(V+E), where V is the number of vertices and E is the number of edges.

Reason: V for storing the vertices in the queue and E for storing the edges in the adjacency vector. 

Frequently Asked Questions

What is Kahn’s algorithm?

It is an algorithm used to find the topological ordering of vertices of a graph.

Is topological sorting BFS or DFS?

Topological sorting can be done using both BFS and DFS. However, Khan’s algorithm uses BFS. 

What is topological sorting?

Topological sorting is a linear ordering of vertices of a graph such that for every directed edge from u to v, u comes first in the ordering.

What is the time complexity of Kahn’s algorithm?

The time complexity of Kahn’s algorithm is O(V+E), where V is the number of vertices and E is the number of edges.

Where can I submit my “Course schedule” code?

You can submit your code on Coding Ninjas Studio here and get it accepted right away.

Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?

Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Conclusion

In this article, we’ve discussed a problem that required topological ordering to be found out. One of the ways to find out the topological ordering was using Kahn’s algorithm. You can also find it out using DFS Algorithm. For more details on this, refer to this article here. Also, there are many problems related to topological sorting like 

• Topological sort,  
• course schedule II 
• detect cycle in a directed graph.

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!