【Ruby実装あり】トポロジカルソートって何？

1. はじめに

トポロジカルソートというアルゴリズムを学習したため、アウトプットしようと思います。
また、今回の記事では、トポロジカルソートの基本概念からアルゴリズム、実装例（Ruby）までの解説を試みます。

2. トポロジカルソートの概要

トポロジカルソートは、有向非巡回グラフ（DAG：Directed Acyclic Graph）の頂点を線形に並べる手法です。

「有向非巡回グラフ」がすでに難しいと思うので、「有向」と「非巡回」に分けて説明します。

まず、「有向グラフ」とは、「頂点」と「向きのついた辺」からなるグラフのことです。
イメージ的には、丸い図形を頂点とすると頂点が複数あり（仮にA〜Cまでがあるとします）、その頂点同士を結ぶ辺が頂点Aから頂点Bと頂点C,頂点Bからは頂点Cに向かって矢印で描かれている様子などを思い浮かべていただくと良いかと思います。

そして「有向非巡回グラフ」とは、「有向グラフ」が巡回しないということです。
先ほどの例を用いると、頂点Cから頂点Aに向かって矢印が描かれていないということです。

この並べ替えにより、すべての有向辺が前から後ろへ向かう順序になります。
例として、プロジェクトのタスク管理やビルドの依存関係が挙げられます。
グラフ内にサイクルが存在するとソートできないため、DAGが前提となります。

各頂点は、あるタスクや要素に対応し、依存関係が辺として表されます。
正しい順序を求めることで、処理の前後関係が明確になります。
アルゴリズムの出発点は、入次数が「0」の頂点から順次処理する方法です。

またこの「入次数」が難しいと思うのですが、「その頂点に向けられている辺の数」のことです。
先ほどの頂点A〜Cの例だと、頂点Aの入次数は0、頂点Bの入次数は1、頂点Cの入次数は2　となります。

このDAGは、グラフ理論における順序決定の基礎として広く用いられているそうです。

3. アルゴリズムの詳細

トポロジカルソートを行うための代表的なアルゴリズムには①Kahnのアルゴリズム（Kahnさんが考案）と ②深さ優先探索ベースの方法があります。
今回は、Kahnのアルゴリズムを中心に説明します。

まず、各頂点の入次数を計算し、入次数が「0」の頂点をキューに入れます。
その後、キューから頂点を取り出し、結果リストに追加します。
取り出した頂点に隣接する頂点の入次数を減らし、新たに「0」になった頂点をキューに追加します。
この手順をすべての頂点が処理されるまで繰り返します。
途中で複数の頂点が同時に入次数「0」になれば、一意な順序ではなくなる可能性があります。
また、全頂点が処理できなければサイクルが存在することになります。
各ステップの処理と一意性の確認がポイントです。

4. 実装例（Ruby）

Ruby を使ったトポロジカルソート（Kahnのアルゴリズム）の実装例を解説します。
状況としては、1,2,3,4の4種類の紐があり、伝えられた比較結果から紐の長さ順を1通りに定めることができるか判定したいとします。

◎ 比較結果
1の紐 > 2の紐
1の紐 > 3の紐
2の紐 > 3の紐
3の紐 > 4の紐

そして、上記比較結果は以下の形で入力されると仮定します。

1 2
1 3
2 3
3 4

最終的には、1通りに定められる場合には下記のような長い紐から順に並べた出力をし、1通りに定められない場合は-1を出力するようにします。

1 2 3 4

上記を踏まえた場合の実装が下記です。

# n : 紐の種類
n = 4

# m : 比較結果の数
m = 4

# 「より長い」から「より短い」への関係を格納するための配列
graph = Array.new(n + 1) { [] }
# 各鉱物の入次数を記録する配列（初期値は 0）
indegree = Array.new(n + 1, 0)

# グラフと入次数を構築する
m.times do
  h, s = gets.split.map(&:to_i)
  graph[h] << s     # 「h > s」なので、hからsへの有向辺を追加
  indegree[s] += 1  # sの入次数を1増やす
end

# この時点では以下のようになっている
# graph[[][2,3][3][4]]
# indegree[0, 0, 1, 2, 1]

# トポロジカルソート
queue = []  # 入次数0の頂点を格納する配列(上記indegreeだと、初回はqueueに1が入る)
(1..n).each do |i|
  queue << i if indegree[i] == 0
end

order = []  # 順番に並べた結果を保存する配列

while !queue.empty?
  # もし頂点が複数ある場合、一意な順番とならないので -1 を出力して終了
  if queue.size > 1
    puts -1
    exit
  end

  # queue から一つ取り出す（入次数が0の唯一の紐）
  current = queue.shift
  order << current

  # current（最も長い紐）から出る各辺について、隣接する頂点の入次数を１ずつ減らす
  graph[current].each do |next_node|
    indegree[next_node] -= 1
    # 入次数が 0 になったら、queue に追加する
    queue << next_node if indegree[next_node] == 0
  end
end

# もし全ての頂点を処理できなかった場合（=サイクルが存在する場合）は -1 を出力
if order.size != n
  puts -1
else
  # 結果を半角スペースで区切って出力
  puts order.join(" ")
end

5. 最後に

ソートアルゴリズムとしては、バブルソートやクイックソートなどは知っていたものの、トポロジカルソートは知らなかったため勉強になりました。
情報系を出ていない自分にとって、初耳のアルゴリズムはちょっと身構えてしまうのですが、実装して理解してみると思ったほど複雑ではないような気もしました（実際のケースで使うとなると難しいのかもですが、、笑）