トポロジカルソート
プログラミングコンテストでは「トポロジカルソート」と呼ばれるソート（ならべかえ）を行う必要がある問題が出題されることがあります（たとえば、AtCoder ABC 223 D問題など）。
そこで、ここでは python3 を用いて「トポロジカルソート」を、初学者向けに、実装する方法を紹介します。
トポロジカルソートとは？
まず、はじめにトポロジカルソートを調べてみると、「有向非巡回グラフ（DAG）」などの難しい言葉がでてきます。
ここではそのような表現は使わず、あえてざっくりと言えば、トポロジカルソートは「優先順位を意識して並べ替えを行う」ことといったところでしょうか。
具体例として、上記の ABC 223 D問題の入力例1 をとりあげます。
とりあえず、下の図1をごらんください。
まず、ここでは４つの頂点があります。
そして、「頂点2」 および 「頂点4」 から矢印が出ています。
これがトポロジカルソートを行う上での肝で、
ここでは 「頂点2」は「頂点1」および「頂点4」より優先され、
さらに「頂点3」は「頂点4」より優先されるということを意味しています。
それらの制約条件（＝優先順位）を意識して並べ替えるのが「トポロジカルソート」となります。
（図1）で考えられる結果は、複数あり、以下の５パターンが考えられます。
・2 → 1 → 3 → 4
・2 → 3 → 1 → 4
・2 → 3 → 4 → 1
・3 → 2 → 1 → 4
・3 → 2 → 4 → 1
ちなみに、ABC 223 D問題 では、それらの結果の中から、辞書順で最小のものを答えるようになっているので、
2 → 1 → 3 → 4 が答えになります。
それでは以下にpython3でトポロジカルソートを実装していきます。
トポロジカルソートのpython3での実装例
さっそくですが、以下がトポロジカルソートの実装例になります。
ここでは、ABC 223 D問題 で与えられる、入力等のフォーマットに準じていますのでご注意ください。
# 0) 入力部
N, M = map(int, input().split()) # N: 頂点数、M: 制約条件数
# 1) 状態を記録するリストの宣言
indeg = [0] * N # 頂点 n に流入するノード数 を記録するリスト
out = [[] for n in range(N)] # n から流出するノードの集合 を記録するリスト
# 2) 制約条件の入力と、状態の記録
for m in range(M):
a, b = map(int, input().split())
a, b = a-1, b-1 #indexの開始番号を0に変更
indeg[b] += 1
out[a].append(b)
#print(indeg)
#print(out)
# 3)トポロジカルソート
import heapq
s = [] #流入する頂点がない（= 並べ替えの答えとして使っても良い！）頂点を記録するリスト
heapq.heapify(s)
ans = [] #並べ替えの結果を記録するリスト
# 流入する頂点数が0の頂点を s に代入
for i in range(N):
if indeg[i] == 0:
heapq.heappush(s, i)
# s から最小の値を取り出して、ansに加える行為を、
# s が空になるまで続ける
while s:
i = heapq.heappop(s) #最小値の取り出し
ans.append(i+1) #答えへの付加 ※indexの開始番号を1に戻しています
#答えとして使用した頂点から流入する頂点の数を減らす
for j in out[i]:
indeg[j] -= 1
#print(ans, i, out, indeg)
#減らした結果、先行する頂点がなくなった場合は s に追加
if indeg[j] == 0:
heapq.heappush(s, j)
# 4) 出力部
if len(ans) != N:
print(-1)
else:
print(' '.join(map(str, ans)))解説
上記コードの肝は、
「indeg」 と 「out」 と名付けた２つのリストに状態を記録している部分です。
「indeg」の役割は、その頂点に流入するノード数を記録することです。
すなわち、ある頂点 n の前に来るべき頂点の数が何個あるかを記録します。
ですから、初期入力が終わった段階では 「indeg」の値は 、
[1, 0, 0, 2]となります。indeg[1] および indeg[2] の値が 0 になっており、これは（図1）における、頂点2 と頂点3 の前に来るべき頂点はないことを意味しています。
一方で、「out」の役割は、その頂点から流出する頂点の番号を記録することです。「indeg」は数を記録していましたが、「out」 では数ではなく具体的な頂点番号を記録しています。
初期入力が終わった段階での「out」の値は、
[[], [0, 3], [3], []]となります。
コード中の 3) の部分でトポロジカルソートを行っています。
ここでは、「heapq」を使用しています。これは ABC 223 D問題 では、辞書順で最小のものを答えるように求められているからであり、それを気にしなくて良ければ「deque」でも実装可能です。
流れとしては、
・流入する頂点数が 0 のものを、「indeg」で確認して、s と名付けたリストに追加。
・s が空になるまで、以下の処理を行う。
・s から頂点番号を取り出し、ans と名付けたリストに追加。
・先程、ans に追加した頂点から流出する頂点の番号を「out」で確認して、それぞれの流入する頂点数を -1 する（「indeg」中で）。
・-1 した時点で、その値が 0 になっていれば、その頂点番号を s に追加。
・ans にトポロジカルソートされた頂点が格納されている。
また、コード中では、例えば（図2）のように、「頂点1」「頂点2」の間でループが発生していると、トポロジカルソートができないので、できない場合に -1 を出力するための処理です。
最後に、deque を用いた実装も下に載せておきます。
この場合の答えは、heapq の場合が 2 → 1 → 3 → 4 であったのに対し、2 → 3 → 1 → 4 となります。
# 0) 入力部
N, M = map(int, input().split()) # N: 頂点数、M: 制約条件数
# 1) 状態を記録するリストの宣言
indeg = [0] * N # 頂点 n に流入するノード数 を記録するリスト
out = [[] for n in range(N)] # n から流出するノードの集合 を記録するリスト
# 2) 制約条件の入力と、状態の記録
for m in range(M):
a, b = map(int, input().split())
a, b = a-1, b-1 #indexの開始番号を0に変更
indeg[b] += 1
out[a].append(b)
#print(indeg)
#print(out)
# 3)トポロジカルソート
from collections import deque
s = []
s = deque(s)
ans = []
for i in range(N):
if indeg[i] == 0:
s.append(i)
#print(s)
while s:
i = s.popleft()
ans.append(i+1)
for j in out[i]:
indeg[j] -= 1
if indeg[j] == 0:
s.append(j)
# 4) 出力部
if len(ans) != N:
print(-1)
else:
print(' '.join(map(str, ans)))
お役に立てれば幸いです！
