🟡 Graph Algorithms: Course Schedule

AIVIA Project Engine Coding Challenges
1

Graph Algorithms: Course Schedule

Difficulty: Medium

Problem Statement

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, represented as a list of pairs where prerequisites[i] = [ai, bi] indicates that you must take course bi before course ai.

Given the course prerequisites, return a possible order in which you can finish all courses. If it’s impossible to finish all courses (due to a cycle), return an empty list.

Implementation Details

Implement the following function:

def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    """
    Determine an order in which all courses can be finished.

    Args:
        num_courses (int): The total number of courses.
        prerequisites (List[List[int]]): The list of prerequisite pairs.

    Returns:
        List[int]: A list of course indices in the order they should be taken. Return an empty list if impossible.
    """
    pass  # Your implementation here

Constraints

  • Number of Courses: (1 \leq \text{num_courses} \leq 10^4)
  • Number of Prerequisites: (0 \leq \text{len(prerequisites)} \leq 10^5)
  • Prerequisites Pairs: Each element in prerequisites is a pair [ai, bi] with (0 \leq ai, bi < \text{num_courses}).

Example Usage

num_courses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
print(find_order(num_courses, prerequisites))
# Expected Output: [0,1,2,3] or [0,2,1,3] (Any valid topological order)

num_courses = 2
prerequisites = [[1,0],[0,1]]
print(find_order(num_courses, prerequisites))
# Expected Output: [] (It's impossible due to a cycle)

Test Cases

def test_find_order():
    # Test Case 1: Simple linear dependency
    assert find_order(2, [[1,0]]) == [0,1]

    # Test Case 2: Multiple valid orders
    order = find_order(4, [[1,0],[2,0],[3,1],[3,2]])
    assert order in ([0,1,2,3], [0,2,1,3])

    # Test Case 3: Cycle exists
    assert find_order(2, [[1,0],[0,1]]) == []

    # Test Case 4: No prerequisites
    order = find_order(3, [])
    assert set(order) == {0,1,2}

    # Test Case 5: Disconnected components
    order = find_order(5, [[1,0],[2,3]])
    assert set(order) == {0,1,2,3,4}
    assert order.index(1) > order.index(0)
    assert order.index(2) > order.index(3)

    print("All test cases pass!")

Expected Solution Approach

This problem requires constructing a Topological Sort of the courses based on the prerequisites.

Algorithm Steps

  1. Build the Graph:

    • Represent courses as nodes in a graph.
    • For each pair [ai, bi], add an edge from bi to ai.

  2. Detect Cycles and Perform Topological Sort:

    • Use Depth-First Search (DFS) with cycle detection:
      • Mark each node as unvisited, visiting, or visited.
      • If you encounter a node that is currently being visited (visiting), a cycle exists.
    • Alternatively, use Kahn’s Algorithm (BFS approach):
      • Calculate in-degrees of nodes.
      • Initialize a queue with nodes having zero in-degree.
      • Remove nodes from the queue, reducing the in-degree of their neighbors.

  3. Return Result:

    • If a valid ordering is found, return it.
    • If a cycle is detected and not all courses can be completed, return an empty list.

Time Complexity

  • Time Complexity: (O(V + E)), where (V) is the number of courses and (E) is the number of prerequisites.
  • Space Complexity: (O(V + E)) for storing the graph and the in-degree/count arrays.

Implementation Hint

Here’s a skeleton using Kahn’s Algorithm:

from collections import deque, defaultdict

def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    # Build the graph and compute in-degrees
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    # Initialize queue with courses having zero in-degree
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check if a valid order is possible
    if len(order) == num_courses:
        return order
    else:
        return []

Learning Objectives

  1. Understand Graph Traversal Algorithms:

    • Implement topological sorting.
    • Recognize when to use BFS or DFS in graph problems.

  2. Detect Cycles in Directed Graphs:

    • Identify cycles that prevent valid orderings.
    • Apply cycle detection techniques in DFS.

  3. Manage Dependencies:

    • Model prerequisite relationships.
    • Handle scenarios with multiple independent sequences.

  4. Optimize Algorithm Performance:

    • Analyze time and space complexity.
    • Efficiently process large graphs with many nodes and edges.

Real-World Applications

  • Course Planning: Determine feasible sequences of courses based on prerequisites.
  • Build Systems: Order compilation of code modules with dependencies.
  • Task Scheduling: Plan tasks that depend on the completion of other tasks.
  • Dependency Resolution: Install software packages considering their dependencies.