\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年12月27日 星期日

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點,就是"隨機拆牆"。
一開始假設所有牆都在,也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”,那麼就隨機選擇一堵牆,要求牆兩端的格子不連通,即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉,即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去,直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法,需要用到並查集

範例生成圖:
#########################
#   #       #   #       #
### # # # ### ####### ###
#     # #   #   # #     #
######### ### # # ##### #
#       # #   #   #     #
### ### # # # ### ### ###
#   #   #   #   #       #
### # ##### ### ##### ###
#   #       # #     # # #
####### # ### # ####### #
#   # # #   #       # # #
# ### ### ### # ##### # #
# #     # #   # # # # # #
# # ### # ### ### # # # #
# # #     #   #         #
# # ### ######### # #####
#   #   # # #     #   # #
####### # # # # ### ### #
#     #       #   #     #
# # ##### ######### # ###
# #               # #   #
### # # ### # ####### ###
#   # #   # #   #       #
#########################

code(n,m必須是奇數):

沒有留言:

張貼留言