はじめに

タイトルにあるように、この記事ではグラフ理論における概念の一つである最小全域木というものを用いて、迷路を作成する方法について記述しています。なお、筆者はグラフ理論をしっかり学んでいるわけではないため、最小全域木について誤解している部分があるかもしれませんがその際は進んでご指摘ください。

迷路の定義

この記事においては、迷路をグラフ理論における木であると定義します。下図のように、基本的に迷路は頂点と辺の組み合わせで表現することができ、かつ連結で頂点数-1の辺を持つため迷路を木で表現することは妥当であるといえます¹。

図1 迷路と木の関係

全域木

ところで、木には二分木や平衡木などいくつかの種類が存在します。その中に、全域木というものが存在します。数学的な定義は省きますが、簡単に言えば全域木とは、「あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木」です²(図2参照)。 特に、元となるグラフの辺に正の数の重みが設定されている場合、全域木を構成する辺の重みの総和を計算することができ、この重みの総和が最小となるように構成された全域木を最小全域木といいます。 図2 全域木

先の迷路の定義から、迷路を作成するというのはグラフの全域木を求めることと同値であることがわかります。

迷路生成アルゴリズム

前項で示したように、迷路作成は全域木を求めることと同値であるため、全域木を求めるアルゴリズムが組めれば、迷路作成アルゴリズムが組めることになります。 そこで、今回はクラスカル法を用いて全域木を生成することにします³。ただし、簡単のため次の前提条件を設定します。

• 元となるグラフは二次元配列A[H][W]で、A[y][ｘ]は頂点v(x + yW)を表す
• 辺集合は配列Eで、要素としてタプルt(v(a), v(b), w)を持つ
• タプルtは、頂点v_a, v_b間の重みがwという意味を表す
• w >= 0を満たし、w = 0は頂点v(a), v(b)が隣接していないことを表す
• wは上の条件を満たす乱数

アルゴリズムの詳細は次の通りです。

1. Aの各要素を要素数1の木の集合Tとして、集合族Fに保存する
2. Eが空集合となるまで、Eから最小のwをもつtを取り出す
3. tの頂点v(a), v(b)がそれぞれFの異なる集合T(a), T(b)に属していれば、T(a), T(b)を合成し一つの木とする
4. 2に飛ぶ

このアルゴリズムを実行することで、最終的にAのすべての頂点から構成される一つの木が生成されます。これがAの全域木、すなわち迷路となります。

実行結果

上記のアルゴリズムを実装したプログラムを実行した際の結果を下に示します。 図3 クラスカル法により生成された迷路1

図4 クラスカル法により生成された迷路2

おわりに

迷路の生成方法の一つとして、全域木を用いたアルゴリズムを紹介しましたが、他の有名な迷路生成方法である棒倒し法や穴掘り法と比べ、比較的アルゴリズムが複雑だと思います。 ですが、迷路が生成できる論理的な理由が最もわかりやすいアルゴリズムだと思うので、迷路生成方法の一つとしてぜひ検討してみてください。

迷路生成で用いたコードを見たいという方は、こちらのmasterブランチのmain.cppを見てください。かなり見にくいコードですが、実装の参考になれば幸いです。

参考文献