トポロジカルソート

OYPosted by

久々にアルゴリズムの本再開しました。

今グラフアルゴリズムまわりをざっと目を通してます。

小難しい数式とかクソご丁寧すぎる説明は全部スルーしてるので読んだ文字数は結局2割程度。サクサク進みます。
時間も体力も集中力も記憶量も限界があるから、物好きか怪物でもない限りは最低限だけキャッシュしてあとは学術書を辞書的に使えるようにするのがベストですね。

 

さて本題です。
小難しい話は嫌だ!って人はそのまま動かせるソースコードを最後に添付してあるのでコピペして動かしてみたり解読するだけでもいいと思います。

トポロジカルソートとは

依存関係を有向非巡回グラフで表した場合に、その依存関係を充足した上で一次元配列にソートするためのアルゴリズムです。

わかりやすく説明するために例を、
我々はズボンを履く前に靴を履いたりはしないですよね。この場合、ズボン→靴の依存関係があるということになります。我々は毎日、衣服(帽子、上着、ネクタイ、etc)を着る順番をトポロジカルソートによって得ています。

また、ミドルウェアなどのインストールを行ったことがある人にはmakefile、makeコマンドなどをご存知の方も多いと思います。あれもトポロジカルソートの実用例であり、makefileに依存関係を記述することでそれらを解決した上でインストールを行うことができます。

トポロジカルソートの実際の処理は有向非巡回グラフに対して深さ優先探索を適用し、各ノードを探索が完了した順番の逆順にソートするというもの。

深さ優先探索についてざっくり必要な部分(というか流れ)だけ説明すると、

  1. rootノードを選択
  2. 未探索の子ノードへ移動(開始時間を記録する)
  3. 子ノードが全て探索し終わったら完了時間を記録し、親ノードへ移動する
  4. (2、3繰り返し)
  5. 1.で選んだrootノードが探索し終わって、まだ未探索のノードが残っている場合、再度1.で別のrootノードを選択する。

ざっくりすぎて抜けがあるかもだけどだいたい手順は上記の通り。後述するコードを見れば一目瞭然なのでそちらを見た方が早いかも。

肝心な、「なぜ深さ優先探索適用後のグラフを探索完了時間で逆順ソートすれば依存関係が解決されるのか」を説明してないのですが、完全証明とかでなければじっくり考えれば直観的に分かるので自分で調べるなり考えるなりしてほしい(疲れた)。

以下ソースコード

ーーーーーーーーーーーーーー
実行結果
ーーーーーーーーーーーーーー
パンツ
靴下
シャツ
ネクタイ
ズボン
ベルト
上着
帽子

ーーーーーーーーーーーーーー

やっぱJava8のStreamAPIがすごく便利ですね。他に関数型インターフェース、ラムダ、メソッド参照とか使い慣れると、Java8未満のプロジェクトにぶち込まれたらストレスで死ぬと思います。

Leave a Reply

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

CAPTCHA