迷路はじめにタイトルにあるように、この記事ではグラフ理論における概念の一つである最小全域木というものを用いて、迷路を作成する方法について記述しています。筆者はグラフ理論をしっかり学んでいるわけではないため、最小全域木について誤解している部分があるかもしれませんがその際は進んでご指摘ください。迷路の定義この記事においては、迷路をグラフ理論における木であると定義します。下図のように、基本的に迷路は頂点と辺の組み合わせで表現することができ、かつ連結で頂点数-1の辺を持つため迷路を木で表現することは妥当であるといえます1。全域木ところで、木には二分木や平衡木などいくつかの種類が存在します。その中に、全域木というものが存在します。数学的な定義は省きますが、簡単に言えば全域木とは、「あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木」です0。元となるグラフの辺に正の数の重みが設定されている場合、全域木を構成する辺の重みの総和を計算することができ、この重みの総和が最小となるように構成された全域木を最小全域木といいます。先の迷路の定義から、迷路を作成するというのはグラフの全域木を求めることと同値であることがわかります。迷路生成アルゴリズム前項で示したように、迷路作成は全域木を求めることと同値であるため、全域木を求めるアルゴリズムが組めれば、迷路作成アルゴリズムが組めることになります。そこで、今回はクラスカル法を用いて全域木を生成することにします2。簡単のため次の前提条件を設定します。v(b)が隣接していないことを表すwは上の条件を満たす乱数アルゴリズムの詳細は次の通りです。T(b)を合成し一つの木とする2に飛ぶこのアルゴリズムを実行することで、最終的にAのすべての頂点から構成される一つの木が生成されます。これがAの全域木、すなわち迷路となります。上記のアルゴリズムを実装したプログラムを実行した際の結果を下に示します。クラスカル法により生成された迷路2おわりに迷路の生成方法の一つとして、全域木を用いたアルゴリズムを紹介しましたが、他の有名な迷路生成方法である棒倒し法や穴掘り法と比べ、比較的アルゴリズムが複雑だと思います。迷路が生成できる論理的な理由が最もわかりやすいアルゴリズムだと思うので、迷路生成方法の一つとしてぜひ検討してみてください。迷路生成で用いたコードを見たいという方は、こちらのmasterブランチのmain.cppを見てください。見にくいコードですが、実装の参考になれば幸いです。