Topological Sorting to Determine Course Order

The problem is to determine the order in which courses should be taken given their prerequisites. This can be represented as a Directed Acyclic Graph (DAG), where courses are nodes, and edges represent the prerequisites.

Approach

The approach used here is Topological Sorting using BFS (Kahn’s Algorithm). The idea is to check if the courses can be arranged in a sequence such that for every directed edge U -> V, course U comes before course V.

Key Steps:

1. Create an Adjacency List:

   • The adjacency list represents the graph where each node (course) points to its dependent nodes (courses that depend on it as a prerequisite).

2. Calculate In-Degrees:

   • In-degree of a node is the number of edges pointing to it. Courses with zero in-degrees can be taken without any prerequisites.

3. BFS Traversal:

   • Start from the nodes with zero in-degrees, and reduce the in-degrees of their neighboring nodes. If a node's in-degree becomes zero, it means all its prerequisites have been met, and it can be added to the course order.

4. Check for Completion:

   • If all courses are included in the topological order, a valid order exists. Otherwise, it's impossible to complete all courses.

Code Explanation

#include <iostream>
#include <list>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
  // Function to perform Topological sort using BFS traversal
  vector<int> topoLogicalSort_BFS(int numNodes, unordered_map<int, list<int>> &adjacencyList) {
    queue<int> bfsQueue; // Queue for BFS traversal
    unordered_map<int, int> inDegree; // Map to store in-degrees of nodes
    vector<int> result; // Result vector to store topological order

    // Count in-degrees of each node
    for (int i = 0; i < numNodes; i++) {
      for (auto neighbor : adjacencyList[i]) {
        inDegree[neighbor]++;
      }
    }

    // Add nodes with 0 in-degrees as starting points
    for (int i = 0; i < numNodes; i++) {
      if (inDegree[i] == 0) {
        bfsQueue.push(i);
      }
    }

    // Perform BFS traversal
    while (!bfsQueue.empty()) {
      int currentNode = bfsQueue.front(); // Extract the front node for processing
      bfsQueue.pop();
      result.push_back(currentNode); // Add the node to the result

      // Visit neighbors, decrease their in-degrees, and enqueue if in-degree becomes 0
      for (auto neighbor : adjacencyList[currentNode]) {
        inDegree[neighbor]--;
        if (inDegree[neighbor] == 0) {
          bfsQueue.push(neighbor);
        }
      }
    }

    return result; // Return the topological order
  }

  // Function to return the order of courses according to their dependencies
  vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
    unordered_map<int, list<int>> adjacencyList;

    // Build the adjacency list
    for (auto prerequisite : prerequisites) {
      int course = prerequisite[0];
      int prerequisiteForCourse = prerequisite[1];
      adjacencyList[prerequisiteForCourse].push_back(course);
    }

    // Get the topological order of courses
    vector<int> topologicalOrder = topoLogicalSort_BFS(numCourses, adjacencyList);

    // Return the topologicalOrder if all courses can be arranged, else return an empty vector
    return (topologicalOrder.size() == numCourses) ? topologicalOrder : vector<int>();
  }
};

int main() {
  Solution solution;

  int numCourses = 4;
  vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};

  vector<int> courseOrder = solution.findOrder(numCourses, prerequisites);

  // Display the result
  if (!courseOrder.empty()) {
    cout << "Course order: ";
    for (int course : courseOrder) {
      cout << course << " ";
    }
    cout << endl;
  } else {
    cout << "No valid course order exists." << endl;
  }

  return 0;
}

Time Complexity
O(V + E), where V is the number of vertices (courses) and E is the number of edges (prerequisites). Each node and each edge is processed exactly once.

Space Complexity
O(V + E) for storing the adjacency list and in-degree array.