Detect A cycle in Undirected/Directed Graph using BFS/DFS

Problem Overview

The "Course Schedule" problem on LeetCode (Problem Number 207) is a classic graph problem that requires determining if it is possible to finish all courses given their prerequisites. The problem is integral in understanding dependency management and scheduling tasks, which are pivotal concepts in computer science.

Understanding the Problem

You are given a total number of numCourses and a list of prerequisite pairs. Each pair resembles a directed edge where the first course depends on the second course. Your task is to determine whether you can complete all courses. Essentially, you need to check if there exists a valid ordering of courses such that all prerequisites are completed before taking the course.

Example

Given numCourses = 2, and prerequisites = [[1,0]], it indicates that you need to take course 0 before taking course 1. Hence, it's possible to complete these courses because only one valid order exists: [0,1].

Conversely, for numCourses = 2 with prerequisites = [[1,0],[0,1]], a cycle exists (0 depends on 1, and 1 depends on 0), making it impossible to complete the courses.

Key DSA Concepts and Theory

Graph Representation

The problem is best visualized using a Directed Graph where:

• Each course is a node.
• Each prerequisite pair is a directed edge (pointing from the prerequisite to the dependent course).

Cycle Detection in Graphs

Detecting cycles in directed graphs is crucial as cycles imply unresolvable dependencies which prevent the completion of tasks.

Topological Sorting

A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge u -> v, vertex u appears before v in the ordering. Topological sorting can only be performed on Directed Acyclic Graphs (DAGs). Hence, the problem reduces to detecting if the given graph is a DAG.

Solution Approach

We will utilize Kahn’s Algorithm, a method for topological sorting using BFS, to solve this problem effectively.

Steps

1. Graph Construction:

   • Represent the courses and their prerequisites using adjacency lists.

2. Indegree Calculation:

   • Compute the indegree for each course. Indegree represents the number of prerequisites required for a course.

3. Queue Initialization:

   • Initialize a queue and enqueue all courses with an indegree of 0 (no prerequisite).

4. BFS Traversal (Kahn's Algorithm):

   • Continuously dequeue elements, reducing the indegree of their neighbors. If any neighbor reaches an indegree of 0, enqueue it.
   • Track the number of courses we successfully ordered.

5. Cycle Detection:

   • If the number of ordered courses equals numCourses, no cycle exists, and all courses can be completed. Otherwise, a cycle exists, making completion impossible.

Code Implementation

C++ Code

#include <vector>
#include <queue>

class Solution {
public:
    bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
        std::vector<int> indegree(numCourses, 0);
        std::vector<std::vector<int>> adjList(numCourses);
        
        // Create the graph
        for (const auto& pair : prerequisites) {
            adjList[pair[1]].push_back(pair[0]);
            indegree[pair[0]]++;
        }
        
        // Queue for courses with no prerequisites
        std::queue<int> zeroIndegreeQueue;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0)
                zeroIndegreeQueue.push(i);
        }
        
        int count = 0;
        while (!zeroIndegreeQueue.empty()) {
            int course = zeroIndegreeQueue.front();
            zeroIndegreeQueue.pop();
            count++;
            
            for (int nextCourse : adjList[course]) {
                if (--indegree[nextCourse] == 0) {
                    zeroIndegreeQueue.push(nextCourse);
                }
            }
        }
        
        return count == numCourses;
    }
};

Java Code

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adjList = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<Integer>());
        }
        
        for (int[] pair : prerequisites) {
            adjList.get(pair[1]).add(pair[0]);
            indegree[pair[0]]++;
        }
        
        Queue<Integer> zeroIndegreeQueue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                zeroIndegreeQueue.add(i);
            }
        }
        
        int count = 0;
        while (!zeroIndegreeQueue.isEmpty()) {
            int course = zeroIndegreeQueue.poll();
            count++;
            
            for (int nextCourse : adjList.get(course)) {
                if (--indegree[nextCourse] == 0) {
                    zeroIndegreeQueue.add(nextCourse);
                }
            }
        }
        
        return count == numCourses;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(V + E)

  • V: Number of vertices (courses).
  • E: Number of edges (prerequisite pairs).
  • Each node and edge is visited once.

• Space Complexity: O(V + E)

  • Space required for the adjacency list and queue storage.

Common Mistakes to Avoid

• Ignoring Self-Dependencies: Check if any course directly or indirectly depends on itself.
• Not Updating Indegrees Correctly: Ensure correct decrement of indegrees and queue updates.

Similar Problems on LeetCode

• Course Schedule II (Problem 210)
• Alien Dictionary (Premium)
• Find Eventual Safe States (Problem 802)

Additional Resources and References

• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein for a deeper understanding of graph algorithms.
• Online tutorials and courses such as Coursera or MIT OpenCourseWare for graph theory fundamentals.
• LeetCode Discuss section for solutions and clarifications.

This comprehensive guide should equip you with the understanding needed to tackle this problem and enhance your knowledge of graph algorithms. Good luck with your coding!