LeetCode #207 Course Schedule: ตรวจวงจรด้วย Kahn BFS หรือ DFS สีสามสถานะ

Course Schedule ถามว่าเรียนครบทุกวิชาได้ไหมเมื่อคู่ [course, prerequisite] กำหนด dependency ปัญหานี้เท่ากับตรวจว่า directed graph มีวงจรหรือไม่ ถ้าไม่มีวงจรย่อมมี topological order

วิธี 1: Kahn BFS (แนะนำเป็น default)

นับ indegree ของแต่ละวิชา เริ่ม queue ด้วยวิชาที่ไม่มี prerequisite แล้วค่อยลด indegree ของวิชาถัดไป ถ้าประมวลผลได้ครบ num_courses แปลว่าไม่มีวงจร จุดเด่นคือเปลี่ยนต่อให้คืนลำดับวิชาได้ง่าย

วิธี 2: DFS สีสามสถานะ

สถานะ 0 คือยังไม่เห็น, 1 คืออยู่ใน recursion path, 2 คือจบแล้ว ถ้าเดินไปเจอโหนดสี 1 แปลว่าพบ back edge และวงจร โค้ดสะท้อนนิยามวงจรตรงๆ แต่ graph ยาวมากอาจชน recursion limit ของ Python

from __future__ import annotations

import unittest
from collections import deque


def can_finish_kahn(n: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for course, before in prerequisites:
        graph[before].append(course)
        indegree[course] += 1

    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    visited = 0
    while queue:
        node = queue.popleft()
        visited += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return visited == n


def can_finish_dfs(n: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(n)]
    for course, before in prerequisites:
        graph[before].append(course)
    state = [0] * n

    def acyclic(node: int) -> bool:
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True
        state[node] = 1
        if not all(acyclic(nxt) for nxt in graph[node]):
            return False
        state[node] = 2
        return True

    return all(acyclic(node) for node in range(n))


class CourseScheduleTests(unittest.TestCase):
    def test_both_methods(self):
        cases = [
            (2, [[1, 0]], True),
            (2, [[1, 0], [0, 1]], False),
            (1, [], True),
            (3, [[1, 0], [2, 1], [0, 2]], False),
        ]
        for solve in (can_finish_kahn, can_finish_dfs):
            for n, edges, expected in cases:
                self.assertEqual(solve(n, edges), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Kahn BFS	DFS สามสี
เวลา / พื้นที่	O(V+E) / O(V+E)	O(V+E) / O(V+E)
คืน topological order	ตรงไปตรงมา	ต้องเก็บ postorder
หา cycle path	ต้องเพิ่ม parent logic	ต่อได้ง่ายกว่า
graph ลึกมาก	ปลอดภัยกว่า	เสี่ยง recursion limit
input ต้อง sort	ไม่ต้อง	ไม่ต้อง
mutation input	ไม่มี	ไม่มี
streaming edges	ต้องสร้าง adjacency/indegree	ต้องสร้าง adjacency

ใช้ Kahn เป็น default สำหรับ Python และงานที่อยากได้ลำดับต่อ ใช้ DFS เมื่อทีมคุ้นกับ traversal และต้องต่อยอดหาเส้นทางวงจร

Recap

• วางทิศ edge จาก prerequisite ไป course ให้ถูก
• เทียบจำนวนโหนดที่ประมวลผล ไม่ใช่จำนวน edge
• เทสต์ graph ว่าง, self/cycle และโหนดโดดเดี่ยว
• เลือก iterative BFS เมื่อ graph อาจลึกมาก