再帰関数書きたくない！！！(トポロジカルソート編)
この記事は異世界行ったら本気だすぴょこりんクラスタ Advent Calendar 2021のために書いたものです。このアドベントカレンダーそのものに関しては、主催者による紹介記事を見てください。
はじめに
再帰関数はとっても便利なもので、これを使うと アルゴリズムがシンプルに実装できることがありますね。 競技プログラミングでもよく使われますが、 pythonだとどうしてもこういうのを書かざるを得ません。
import sys sys.setrecursionlimit(200000)
これ、美しさを損ねている感じがしますし、なるべくなら書きたくないですよね。 それに、たかだかスタック領域のサイズ分しか入力を扱えないというスケーラビリティの問題もあります。 なので、書かないでなんとかしましょう。
今回はトポロジカルソートを再帰なしで書いてみます。
トポロジカルソートとは？
Directed Acyclic Graphという、辺に向きがあってかつサイクルがないグラフの 並び替えです。辺の指し元が前、指し先が後に来るように並び替えます。 指し元と指し先の順序だけを規定するので、以下の図のように何パターンかあり得ます。
身近なところでは、Makefileがコンパイル順序を決めるのに使っていたりするようです。
トポロジカルソート自体はすごく簡単にできて、深さ優先探索の帰りがけ順にノードを 記録して、最後に逆順にするだけです*1。
やってみましょう
動作確認はここでやりました。
再帰あり版
帰りがけ順なので、自分が指し元となるノード全てに対して深さ優先探索をしたあとで、 自ノードを回答に追加します。
再帰なし版
単にスタックを使うだけ・・・とはいかず、帰りがけ順なので、きちんと自分が 指し元となるノード全てを調べ終えたあとかどうかを判定して、回答に追加します。 再帰を使ったときに比べて長いしわかりにくい感じがしますね。代償が大きくない？
ただ、再帰を使わないおかげで、扱える入力サイズはこちらのほうが大きいですね。
さいごに
まあ再帰使えるときは使ってもいいような気がしてきますね。
