Course Schedule - Java Solution

1. Introduction

This blog post explores the "Course Schedule" problem, an essential problem in graph theory and topological sorting. The challenge is to determine if it's possible to finish all courses given certain prerequisites. This problem is a typical example of detecting cycles in a directed graph, a key concept in computer science and scheduling tasks.

Problem

In a scenario with numCourses courses labeled from 0 to numCourses - 1, and a list of prerequisites represented as a pair [ai, bi] (where you must take course bi before course ai), the task is to determine if it's possible to finish all courses. If it is possible, return true, otherwise return false.

2. Solution Steps

1. Create a graph representing the courses and their prerequisites using an adjacency list.

2. Use depth-first search (DFS) to detect cycles in the graph:

a. Keep track of visited nodes and nodes in the current DFS path.

b. If a node is encountered that is already in the current DFS path, a cycle is detected.

3. Return true if no cycles are found, meaning all courses can be finished; otherwise, return false.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class CourseSchedule {
    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        System.out.println(canFinish(numCourses, prerequisites)); // Test the function
    }

    // Function to check if all courses can be finished
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[1]).add(prerequisite[0]);
        }

        boolean[] visited = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                if (isCyclic(graph, i, visited, recStack)) {
                    return false;
                }
            }
        }
        return true;
    }

    // Helper function to detect a cycle in the graph
    private static boolean isCyclic(List<List<Integer>> graph, int node, boolean[] visited, boolean[] recStack) {
        if (recStack[node]) return true;
        if (visited[node]) return false;

        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : graph.get(node)) {
            if (isCyclic(graph, neighbor, visited, recStack)) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }
}

Output:

true

Explanation:

1. canFinish: This function builds a graph representation of courses and their prerequisites. It then iterates through each course and uses the isCyclic helper function to check for cycles in the graph.

2. The graph is represented as an adjacency list, where each index is a course and the list at each index contains the courses that depend on it.

3. isCyclic: This function performs a DFS on the graph. It uses two boolean arrays, visited and recStack, to keep track of visited nodes and nodes currently in the recursion stack, respectively.

4. If any node in the current DFS path is encountered again, a cycle is detected, indicating that it's impossible to complete all courses (returns false).

5. If no cycles are detected, the function returns true, indicating that it's possible to complete all courses.

6. This approach effectively checks for course dependencies and ensures that no circular prerequisites exist, which would make completing all courses impossible.