Course Schedule 2 Using Topological Sort - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

There are N tasks, labeled from 0 to N-1. Some tasks have prerequisites, meaning a task must be done only after another task is completed. These dependencies are given as pairs [a, b] meaning b must be done before a.

The goal is to return an ordering of tasks that satisfies all the prerequisites. If no valid ordering exists (due to a cycle), return an empty array.

This is a classic case of Topological Sorting in a Directed Graph.

Examples❯

N Prerequisites Output Description
2 [[1, 0]] [0, 1] 0 before 1
4 [[1, 0], [2, 0], [3, 1], [3, 2]] [0, 1, 2, 3] or [0, 2, 1, 3] Multiple valid orderings exist
1 [] [0] Only one task, no prerequisites
2 [[0, 1], [1, 0]] [] Circular dependency, no valid order
3 [] [0, 1, 2] No dependencies, any order is valid

Solution❯

Understanding the Problem

You are given an integer numCourses, which represents the total number of courses labeled from 0 to numCourses - 1. You are also given a list of prerequisite pairs prerequisites, where each pair [a, b] means that you must complete course b before course a.

Your goal is to determine a valid order to take all the courses, such that the prerequisites are respected. If there’s no way to complete all courses due to circular dependencies (cycles), you should return an empty array.

Step-by-Step Solution with Example

Step 1: Represent the problem as a directed graph

Each course is a node. Each prerequisite pair [a, b] becomes a directed edge from b → a. This means course b must come before a.

Step 2: Build the adjacency list and indegree array

The adjacency list keeps track of all courses that depend on a course. The indegree array counts how many prerequisites each course has. 

Input:
numCourses = 4,
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Adjacency List:
0 → [1, 2]
1 → [3]
2 → [3]

Indegree:
[0, 1, 1, 2]

Step 3: Initialize the queue with courses that have zero prerequisites

We can start with courses that have indegree 0 because they don’t depend on any other course.

In this example, course 0 has no prerequisites, so we begin with queue = [0].

Step 4: Perform topological sort using Kahn’s Algorithm

We repeat the following:

  • Pop a course from the queue
  • Add it to the result list
  • Reduce the indegree of all its neighbors
  • If any neighbor’s indegree becomes 0, add it to the queue

Process:
queue = [0]         → result = []
take 0              → result = [0]
decrease indegree of 1 → indegree[1] = 0 → add 1 to queue
decrease indegree of 2 → indegree[2] = 0 → add 2 to queue

queue = [1, 2]
take 1              → result = [0, 1]
decrease indegree of 3 → indegree[3] = 1

take 2              → result = [0, 1, 2]
decrease indegree of 3 → indegree[3] = 0 → add 3 to queue

take 3              → result = [0, 1, 2, 3]

Step 5: Verify result length

If the result contains all numCourses (i.e., length equals numCourses), we have found a valid order. If not, it means there was a cycle.

Edge Cases

  • No prerequisites: If the list is empty, all courses can be taken in any order. For example, numCourses = 3, prerequisites = [] → possible result: [0, 1, 2].
  • Cycle in prerequisites: Example [[1, 0], [0, 1]] forms a cycle. No course order is valid. Return [].
  • Disconnected components: Example [[1, 0], [3, 2]]. These are independent chains and can be solved separately. Valid result: [0, 1, 2, 3] or [2, 3, 0, 1].

Finally

This problem is a classic example of topological sorting in a directed graph. Kahn’s Algorithm is an efficient way to build the course order using a queue and indegree tracking. Always ensure to handle cycles and special cases like no prerequisites or disconnected graphs.

Practicing this problem strengthens your understanding of graph algorithms and helps you apply them in scheduling and dependency resolution scenarios.

Algorithm Steps❯

  1. Initialize an adjacency list graph and an array indegree to count prerequisites for each node.
  2. Fill the graph and indegree based on given prerequisites.
  3. Initialize a queue with nodes having indegree = 0.
  4. While the queue is not empty:
    1. Pop a node from the queue and add it to the result list.
    2. For each neighbor, decrement its indegree.
    3. If indegree becomes 0, enqueue the neighbor.
  5. If the result list contains all tasks, return it. Otherwise, return an empty array.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int graph[MAX][MAX], indegree[MAX], queue[MAX];
int front = 0, rear = -1;

void enqueue(int v) { queue[++rear] = v; }
int dequeue() { return queue[front++]; }

void topologicalSort(int numTasks, int prerequisites[][2], int prereqSize) {
    for (int i = 0; i < prereqSize; i++) {
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
        graph[b][a] = 1;
        indegree[a]++;
    }
    
    for (int i = 0; i < numTasks; i++)
        if (indegree[i] == 0)
            enqueue(i);

    int count = 0;
    while (front <= rear) {
        int curr = dequeue();
        printf("%d ", curr);
        count++;
        for (int i = 0; i < numTasks; i++) {
            if (graph[curr][i] && --indegree[i] == 0)
                enqueue(i);
        }
    }

    if (count != numTasks)
        printf("\nCycle detected. No valid ordering.\n");
}

int main() {
    int prerequisites1[][2] = {{1,0},{2,0},{3,1},{3,2}};
    topologicalSort(4, prerequisites1, 4);
    printf("\n");
    int prerequisites2[][2] = {{0,1},{1,0}};
    topologicalSort(2, prerequisites2, 2);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)In the best case, we visit all vertices and edges once — one pass for building the graph and one pass for processing the queue.
Average CaseO(V + E)Regardless of prerequisites distribution, all vertices and edges are still processed once each.
Worst CaseO(V + E)Even with dense dependencies or cycles, we process each vertex and edge exactly once in topological sort.

Space Complexity❯

O(V + E)

Explanation: We use space for the adjacency list (O(E)), the indegree array (O(V)), the queue (up to O(V)), and the result list (O(V)).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...