我们讨论的最一个问题是迷宫生成，它可能不如前面的洗牌或者排序应用的广泛，但它比较有趣。本节所有算法生成的迷宫本质上是一个二维矩阵网络形式的生成树，也就是说其中没有回路，同时从左下角的起点到迷宫中的每一点都有且仅有一条路径。

      迷宫生成的原理也比较简单，主要就是用到了生成树的一些算法，如果你对广度优先遍历、深度优先遍历、Kruskal算法、Prim算法这些不是很熟悉的话强烈建议你先去看看相应的资料。我们先来看看随机遍历

      算法从左下角开始，每一步从所有可以扩展的点（图中的红点）中随机选择一个进行扩展。注意这个方法看起来可能和广度优先遍历类似，但它们的扩展规则是不一样的。广度优先遍历是严格按照每一层的顺序进行遍历，当前层所有结点遍历完之后才会对下一层进行遍历。

      然后是随机深度优先遍历

      刚才的算法不同，随机深度优先遍历总是从当前最长的路径的末端随机选择一个可扩展点进行扩展，如果出现回路或者抵达边界，那么就回溯到最近的一个可扩展分枝。这种算法生成的迷路分枝相对较少，路径也更长更曲折。

      Prim算法用于构造一棵最小生成树，其边的权重在所有可能的生成树中是最小的。在迷宫生成中，我们可以通过随机指定边的权重，然后就可以使用Prim算法构造出迷宫了~

      Prim算法每一步都从当前最小权重的边中挑一条添加当前迷宫上，如果形成了回路那么将其丢弃，再选一条权重最小的边。

      最后我们再来看一个与众不同的迷宫生成算法

Wilson算法利用擦圈随机游动(loop-erased random walks)的方法生成了一个均匀随机迷宫，实际上就是一棵均匀支撑树(uniform spanning tree)，具体概念可以参考维基百科

      Wilson算法每一轮随机指定一个起始点，然后开始随机游走（图中红色部分），直到其与当前迷宫（图中的白色部分）相交，此时将红色部分变为白色，然后开始下一轮随机游走。如果随机游走的过程中红色部分形成了回路，则将所形成回路擦除，然后继续随机游走。

      不过Wilson算法看起来可能有些无聊，尤其是刚开始的时候，红色部分很难与白色部分相交。但是随着迷宫的规模慢慢扩大，白色部分越来越多时算法运行就较快了。

      回顾我们介绍的四种迷宫生成算法，其原理各不相同，但是仅从结果来看，你可能很难分辨它们之间的区别，毕竟都是眼花缭乱的迷宫嘛~那么我们这里提供一种可以从结果看出迷宫结构（准确的说是生成树结构）的可视化方法——染色法。

      先来看看随机遍历

      我们用颜色来表示生成树的深度，这里用到的是一种类似彩虹颜色的层次表示方法，意会就好~

如果我们把黑色的墙去掉并降低视觉噪声，就可以更精细的观察迷宫的结构，如下图

图中的颜色形成了一层一层的同心圆结构，而且其路径结构也比较单一，没有特别蜿蜒曲折的路径，基本都是沿着一个很小的方向范围前进。当然这与算法的逻辑有很大关系。

随机深度优先遍历则完全不同

      随机深度优先遍历的层次结构要比随机遍历深的多，因为是深度优先嘛，这里彩虹的七种颜色显然不够用了，我们已经完全无法看出结果的层次结构了，只是知道它很复杂。

再来看随机Prim算法

虽然看着有那么一点乱，但是还是可以大致看出其它们之间的层次结构。

最后来看Wilson算法

      看起来是不是和随机Prim算法的结果有一点像？但是我们又被眼睛骗了，结果类似并不能说明两个算法类似，这再次印证了可视化并不是万能。

      考虑到这些迷宫本质上都是生成树，所以我们干脆直接将把迷宫变成生成树的过程可视化，来看看Wilson算法生成的迷宫变成生成树是什么样子

将其和随机深度优先遍历比较一下

      这里两棵生成树的结点数都为3239。用这种方式展示是不是非常直观呢？不过要注意，由于为了适应大小，我们把第二张图缩小了，其生成树的实际深度要远远高于Wilson算法。两张图的生成树的最大深度分别为310和832，而在更大规模的迷宫中，例如有480,000个结点的迷宫，两棵生成树最大深度的有可能会相差10~20倍！所以使用随机深度优先遍历要谨慎啊~

小结

---

      OK，到这里原文的主要内容就结束了，后面就是一些心灵鸡汤部分了（-_-||），什么use vision to think，用视觉思考？好吧，如果你感兴趣可以去看原文~

      这里还是谈谈我的感受吧，回想当初学习数据结构和算法的主要方法就是啃代码，极其枯燥。而且我们的教学形式很久都没有变化了，现在的学生们估计还是要硬生生的去理解代码（-_-），不过这篇《Visualizing Algorithms》却给我们提供了一个很好的思路，那就是把算法变得直观、有趣，从不同角度和层面去剖析一个算法。

      当然这并不是一件容易的事情，首先我们对算法的理解需要更加深入和透彻，否则不可能想出那些神奇的展现方式。其次就是我们的美工水平和前端编程能力，我看了一下原作者网页中可视化实现的一些代码，涉及到CSS、javascript和HTML5（尤其是svg标签和canvas标签的使用）等很多内容，这些没有深厚的功底是做不到的。

我这里再把原文中列出的一些其他算法可视化方面的资源放在这里

（来源 小象学院）