Python – Course Schedule: BFS Topological Sort Approach (DSA) 🚀 #CourseSchedule #PythonDSA #Topolog

This solution solves the Course Schedule problem using a Breadth-First Search (BFS) approach based on Kahn's algorithm for topological sorting. The goal is to determine if it’s possible to complete all courses given a set of prerequisites by checking for cycles in the dependency graph. If a valid topological order exists, all courses can be finished.

What This Solution Covers:

BFS and Topological Sorting:
Kahn's algorithm is used to perform a topological sort by iteratively removing nodes with zero in-degree (no prerequisites).

Graph Construction:
The courses are modeled as a directed graph. Each prerequisite pair [a, b] is represented as an edge from course b to course a.

In-degree Tracking:
We maintain an in_degree list where each element represents the number of prerequisites for that course.

Queue Processing:
We use a deque to process courses with zero in-degree and decrement the in-degree of adjacent courses as they are "taken".

Real-World Applications:
This approach is used in build systems, project scheduling, and dependency resolution tasks.

Step‑by‑Step Explanation:

Graph and In-Degree Initialization:

Construct an adjacency list for the graph where edges point from a prerequisite to a course.

Initialize an in_degree list that counts prerequisites for each course. Code snippet:

graph = {i: [] for i in range(numCourses)}
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
in_degree[course] += 1

#GraphConstruction #InDegree

Queue Initialization:

Populate a queue with all courses that have an in-degree of zero, meaning they have no prerequisites. Code snippet:

from collections import deque
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])

#Queue #BFS

BFS Processing:

Process the queue by removing courses with zero in-degree.

For each course processed, decrement the in-degree of its adjacent courses.

If an adjacent course’s in-degree drops to zero, add it to the queue. Code snippet:

count = 0
while queue:
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:

#TopologicalSort #BFSProcessing

Final Validation:

If the number of processed courses equals numCourses, a valid order exists and all courses can be finished; otherwise, a cycle exists. Code snippet:

return count == numCourses

#Validation #Algorithm

Complete BFS Code:

def canFinish_bfs(numCourses, prerequisites):
from collections import deque
graph = {i: [] for i in range(numCourses)}
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while queue:
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
return count == numCourses

# Example usage:
numCourses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
print("BFS Approach - Can finish courses?", canFinish_bfs(numCourses, prerequisites)) # Expected Output: True

#CourseSchedule #BFS #TopologicalSort #GraphAlgorithms #CodingInterview #PythonDSA