トポロジカルソート

 プログラミングコンテストでは「トポロジカルソート」と呼ばれるソート(ならべかえ)を行う必要がある問題が出題されることがあります(たとえば、AtCoder ABC 223 D問題など)。

そこで、ここでは python3 を用いて「トポロジカルソート」を、初学者向けに、実装する方法を紹介します。

トポロジカルソートとは?

まず、はじめにトポロジカルソートを調べてみると、「有向非巡回グラフ(DAG)」などの難しい言葉がでてきます。

ここではそのような表現は使わず、あえてざっくりと言えば、トポロジカルソートは「優先順位を意識して並べ替えを行う」ことといったところでしょうか。

具体例として、上記の ABC 223 D問題の入力例1 をとりあげます。

とりあえず、下の図1をごらんください。

(図1)ABC223 D問題 入力例1

まず、ここでは4つの頂点があります。

そして、「頂点2」 および 「頂点4」 から矢印が出ています。

これがトポロジカルソートを行う上での肝で、

ここでは 「頂点2」は「頂点1」および「頂点4」より優先され、

さらに「頂点3」は「頂点4」より優先されるということを意味しています。


それらの制約条件(=優先順位)を意識して並べ替えるのが「トポロジカルソート」となります。

(図1)で考えられる結果は、複数あり、以下の5パターンが考えられます。

・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」 と名付けた2つのリストに状態を記録している部分です。

「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 を出力するための処理です。

(図2)トポロジカルソートができない例

最後に、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)))


お役に立てれば幸いです!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です