Pythonで解くコーススケジュール II：DFSによる履修順序の求め方

問題概要

全部で n 個のコース（科目）があり、それぞれ 0 から n-1 までの番号が付けられているとします。一部のコースには先修科目（前提条件）が設定されており、コースの総数と前提条件ペアのリストが与えられたとき、すべてのコースを修了するための履修順序を 1 つ求めるのがこの問題の目的です。

正しい順序は複数存在する場合がありますが、そのうちのどれか 1 つが見つかれば十分です。もし前提条件に循環が含まれていて、すべてのコースを修了することが不可能な場合は、空の配列を返します。

入出力の例

たとえば、入力が 2 と [[1, 0]] の場合、出力は [0, 1] になります。これは、合計 2 つのコースがあり、コース 1 を受講するには事前にコース 0 を修了しておく必要があるためです。したがって、正しい履修順序は [0, 1] となります。

解法のアプローチ

この問題は、グラフ理論におけるトポロジカルソートとサイクル検出を組み合わせた典型的な問題で、DFS（深さ優先探索）を使って解くことができます。手順は以下の通りです。

• メインメソッドでは、numCourses（コース総数）と prerequisites（前提条件リスト）を受け取ります。
• in_degree という配列を定義し、すべてのノードの入次数を格納します。同時に、adj としてグラフの隣接リストも作成します。
• visited という配列を定義し、サイズ numCourses ですべて 0 で初期化します。
• 空のスタックを用意します。
• i を 0 から numCourses-1 までループします。
  • visited[i] が未訪問であり、スタックを渡してノード i から DFS を実行した結果が false の場合は、空のリストを返します。
• 最後に、スタックの要素を逆順にして返します。

実装例

それでは、以下の Python 実装を見て、より深く理解していきましょう。

class Solution(object):
   def findOrder(self, numCourses, prerequisites):
      in_degree,adj=self.create_adj(numCourses,prerequisites)
      visited = [0 for i in range(numCourses)]
      stack = []
      for i in range(numCourses):
         if not visited[i] and not self.dfs(i,visited,stack,adj):
            return []
      return stack[::-1]
   def create_adj(self,n,graph):
      adj = {}
      in_degree= [0 for i in range(n)]
      for i in graph:
         in_degree[i[0]]+=1
         if i[1] in adj:
            adj[i[1]].append(i[0])
         else:
            adj[i[1]] = [i[0]]
      return in_degree,adj
   def dfs(self, node, visited,stack,adj):
      if visited[node] == -1:
         return False
      if visited[node] == 1:
         return True
      visited[node] = -1
      if node in adj:
         for i in adj[node]:
            if not self.dfs(i,visited,stack,adj):
               return False
      visited[node]=1
      stack.append(node)
      return True
ob = Solution()
print(ob.findOrder(2, [[1,0]]))

入力

2
[[1,0]]

出力

[0,1]

アルゴリズムのポイント

visited 配列は 3 つの状態を表しています。0 は「未訪問」、-1 は「現在の DFS パス上にあり探索中」、1 は「探索済み」を意味します。探索中のノードに再び到達した場合はサイクルが存在することを示すため false を返し、すべてのコースの修了が不可能であることを判定します。一方、DFS が完了したノードから順にスタックへ積んでいき、最後に逆順に取り出すことで、依存関係を満たす履修順序（トポロジカル順序）が得られます。