以前写的一个脚本，今天拿来改了下，做了一个彩色的 GIF 图。动图见 github 项目主页
演示的是概率论中的一个算法，叫做 Wilson 一致生成树算法，这个算法的目的是在一个有限图的所有的生成树（此处是网格图，其生成树可以理解为完美迷宫）中以等概率完全随机地取样。这个算法关键的概念是擦圈的随机游动，它维护一个树 T，然后从一个顶点出发，不停的作随机游动，每当遇到回路就擦掉这个回路继续走，直到撞到 T 为止，然后把得到的路径加入 T。重复这个步骤直到所有顶点都在 T 中为止，这时得到的就是一个完全随机的生成树。然后用宽度优先搜索解这个迷宫。染色方案是根据每个顶点到起点的距离染色。
程序用纯 python 写成，不使用任何第三方库／软件，是将整个过程编码为字节流一次输出。生成例子中的图一般几秒十几秒就可以。用 python2 或者 3 都可以运行，大家不妨试一下。
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.