グラフのはなし・その8
さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう.
基本的な構造は昨日の深さ優先探索 (DFS) と同じです.
今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです.
0 -> 1 -> 3
| `-> 4
| V
`-> 2 -> 5
`-> 6昨日のグラフとだいたい同じですが,「4 → 5」の矢印が増えたところが違いますね. ここは後でポイントになりますので, 覚えておいてください.
トポロジカルソートを行う Python スクリプト
# -*- coding: utf-8 -*- class Node(object): def __init__(self, value=0): self.value = value self.checked = False self.children = [] def __str__(self): return 'node{0}'.format(self.value) def __repr__(self): return str(self) # 点の準備 node0 = Node(0) node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) # 矢印の準備 node0.children = [node1, node2] node1.children = [node3, node4] node2.children = [node5, node6] node4.children = [node5] # 探索完了の記録用リスト searched = [] # 分かれ道にきたらこの手順を踏む def dfs(node): print('-> {0.value}'.format(node)) if node.checked: print(u'チェック済み') print('<- {0.value}'.format(node)) return node.checked = True for child in node.children: dfs(child) # さらに分かれ道にきたら同じ手順を繰り返す else: print(u'引き返す') global searched searched.append(node) # 探索が完了したら記録 print(searched) print('<- {0.value}'.format(node)) if __name__ == '__main__': dfs(node0) searched.reverse() print(searched)
昨日のソースコードと違っているところはどこでしょうか?
- searched というリストが増えた.
- dfs というメソッドの終わりの方に searched に node を追加する操作が増えた.
この 2 点だけです.
実行結果は以下のようになりました. 最後の行がトポロジカルソートを行った結果です.
昨日の結果と比べて違っているところはどこでしょうか??
-> 0 -> 1 -> 3 引き返す [node3] <- 3 -> 4 -> 5 引き返す [node3, node5] <- 5 引き返す [node3, node5, node4] <- 4 引き返す [node3, node5, node4, node1] <- 1 -> 2 -> 5 チェック済み <- 5 -> 6 引き返す [node3, node5, node4, node1, node6] <- 6 引き返す [node3, node5, node4, node1, node6, node2] <- 2 引き返す [node3, node5, node4, node1, node6, node2, node0] <- 0 [node0, node2, node6, node1, node4, node5, node3]
もちろんアルゴリズムは変更していないので, 昨日のグラフと今日のグラフの違うところが影響しているわけですね.
今日のグラフは「4 → 5」の矢印が増えているので, 4 の場所まできたときにさらに 5 の場所まで探索できます. それが出力の↓この部分に出ています.
-> 4 -> 5 引き返す [node3, node5] <- 5
考察
さて, 昨日のソースコードには無かった処理「searched.append(node) # 探索が完了したら記録」の部分について考えてみましょう.
当然この部分がトポロジカルソートの肝なのですが,「探索が完了」するとはどういうことでしょうか?
深さ優先探索とは,「探索していないところがあったらどんどん先に進んで, 行き止まりに到達したら引き返す」というものでしたね.
つまりここで言っている「探索が完了」というのは,「ここから行けるところはもう全て探索したよ」という意味なのです.
なので, searched (探索完了) という名前のリスト中のある点 A を見たとき, その点 A から到達できる点は, 必ずそれより前の方にあることになります.
ここがポイントなのですが分かりましたか?
自分でグラフを書いて, 上の処理を 1 つ 1 つ追っていってみてください.
こういうときに重要なのは具体例に対して自分の手を動かすこと.
頭だけで考えただけだと大抵はあやふやな理解しかできていません.
はっきり言いましょう. 手を動かさないで理解した気になっているのは勘違いです!! 手を動かして実験してみてください.
最後に reverse では結果が左右逆になっていて見づらいので, 引っくり返しているのです.
