Pythonでコーススケジュール問題を解く：DFSによるサイクル検出で全コース修了の可否を判定

受講すべきコースが合計 numCourses 個あり、それぞれ 0 から numCourses-1 までの番号が付けられているとします。一部のコースには前提条件（先修科目）があり、たとえば「コース 0 を受講するには、まずコース 1 を修了していなければならない」という関係は、ペア [0, 1] として表現されます。ここで、コースの総数と前提条件のペアのリストが与えられたとき、すべてのコースを修了することが可能かどうかを判定します。

たとえば、入力が numCourses = 2、prerequisites = [[1, 0]] の場合、結果は true になります。受講すべきコースは合計 2 つで、コース 1 を受講するには事前にコース 0 を修了しておく必要がありますが、その順序で履修すればすべて修了できるためです。

解法のアプローチ

この問題は、前提条件を有向グラフとして捉え、グラフ内に循環（サイクル）が存在するかどうかを DFS（深さ優先探索）で検出することで解けます。サイクルが存在すると、どの順序でも履修できないコースが発生するため、全コースの修了は不可能になります。

• メインメソッドは numCourses と prerequisites を受け取ります。
• prerequisites が空の場合は、即座に true を返します。
• 各ノードの訪問状態を記録する配列 visited を作成し、0 で初期化します（要素数は numCourses）。
• adj_list: prerequisites をもとに有向グラフ（隣接リスト）を構築します。
• i を 0 から numCourses-1 までループします。
  • visited[i] が未訪問（0）であれば、そのノードを起点に DFS を実行します。
  • 探索の結果サイクルが検出された場合は、false を返します。
• すべてのノードを確認してもサイクルが見つからなければ、true を返します。

visited 配列の状態管理

サイクル検出では、visited の各要素を次の 3 つの状態で使い分けるのがポイントです。

• 0: 未訪問
• -1: 現在の探索パス上にある（探索中）。この状態のノードに再度到達したらサイクル検出
• 1: 探索完了。そのノードから先にサイクルはないことが確定済み

Pythonでの実装例

以下の実装を見ると、より理解が深まります。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        if len(prerequisites) == 0:
            return True
        visited = [0 for i in range(numCourses)]
        adj_list = self.make_graph(prerequisites)
        for i in range(numCourses):
            if not visited[i]:
                if not self.cycle(adj_list, visited, i):
                    return False
        return True

    def cycle(self, adj_list, visited, current_node=0):
        # 探索中のノードに再び到達した → サイクル検出
        if visited[current_node] == -1:
            return False
        # すでに安全と判明しているノード
        if visited[current_node] == 1:
            return True
        visited[current_node] = -1
        if current_node in adj_list:
            for i in adj_list[current_node]:
                if not self.cycle(adj_list, visited, i):
                    return False
        visited[current_node] = 1
        return True

    def make_graph(self, array):
        adj_list = {}
        for i in array:
            if i[1] in adj_list:
                adj_list[i[1]].append(i[0])
            else:
                adj_list[i[1]] = [i[0]]
        return adj_list

ob = Solution()
print(ob.canFinish(2, [[1,0]]))

入力

2
[[1,0]]

出力

true

計算量

• 時間計算量： O(V + E)。各ノードと各エッジを高々 1 回ずつ処理します（V はコース数、E は前提条件の数）。
• 空間計算量： O(V + E)。隣接リスト・visited 配列・再帰呼び出しスタックのための領域が必要です。

まとめ

コーススケジュール問題は、前提条件を有向グラフとしてモデル化し、DFS でサイクルの有無を判定する典型的なグラフアルゴリズムの問題です。「探索中（-1）」「完了済み（1）」という状態を使い分けることで、効率よく循環を検出できます。この手法は、ビルド依存関係の解決やタスクスケジューリングなど、実際のシステム開発でも広く応用されている重要なテクニックです。