獨立心靈的力量被高估了……真正的力量源自于外部能提高認知能力的幫助。

——唐納德

本文重點研究算法。然而，這里討論的技術適用于更廣泛的問題空間：數學公式、動態系統、過程等。基本上，任何需要理解代碼的地方。

　　那么，為什么要 可視化 算法呢?甚至為什么要去可視化呢?這篇文章將告訴你，如何利用視覺去思考。

算法是可視化中一種迷人的用例。要將一種算法可視化，我們不只是將數據擬合到圖表中，況且也沒有主要的數據集。相反的是有描述行為的邏輯規則。這可能是算法可視化是如此不尋常的原因，因為設計師可以嘗試這種新奇的形式來更好地溝通。這就是來研究它們的充分的理由。

但是，算法也提醒人們——可視化不僅僅只是一種在數據中尋找模式的工具。可視化利用人類的視覺系統，以增加人類的智慧。這樣，我們就可以用它來更好地了解這些重要的抽象過程以及其他事情。

采樣

在解釋第一個算法之前，我首先需要解釋它要解決的問題。

梵高的《星夜》

光(電磁輻射)，從這個屏幕上發出的光，穿過空氣，由你的晶狀體聚焦，并投射到視網膜上，這是一個連續的信號。要被感知，我們必須通過測量其在空間中的不同點的強度和頻率分布把光信號降低到離散脈沖。

這種還原過程被稱為采樣，它對視覺至關重要。你可以把它理解為——一個畫家應用不同的顏色，采用離散的筆觸形成圖像(特別是點畫或點彩派)。采樣其實是計算機圖形學的核心關注點，例如，為了通過光線追蹤來柵格化3D場景，我們必須確定在何處拍攝光線。甚至調整圖像大小也需要采樣。

采樣會因為各種因素的矛盾性而變得困難。一方面要保證采樣點要均勻分布，不要有間隙，另一方面要避免重復采樣或有規律地采樣(否則會產生混疊)。這就是為什么你不應該在照相時穿細條紋襯衫：條紋與相機傳感器中的像素網格產生共振，從而造成莫爾條紋(Moiré patterns)。

圖片來源：retinalmicroscopy.com

這是一張人類視網膜周邊的顯微照片。較大的錐形細胞檢測顏色，而較小的桿細胞改善低光視覺。

人類的視網膜有一個出色的解決方案，在其感光細胞的位置取樣。細胞密集和均勻地覆蓋著視網膜(除了視神經上方的盲點)，然而細胞的相對位置是不規則的。這被稱為泊松盤分布，因為它保持了細胞之間的最小距離，避免遮擋而浪費光感受器。

但是構造一個泊松盤分布是困難的，因此有一個簡單的叫做 Mitchel的近似算法，它是最佳候選算法

從這些點可以看出，最佳候選采樣產生了讓人愉快的隨機分布。這不是沒有缺陷：在一些地區有太多的樣本(過采樣)，而在其他地區是不夠的(欠采樣)。但它相當好，同樣重要的是容易實施。

以下是它的工作原理：

對于每個新樣本，最佳候選算法生成固定數量的候選采樣點，用灰色表示(在這里，這個數為10)。從采樣區域均勻地選擇每個候選采樣點。

最佳候選者，以紅色顯示，是離所有先前樣本(以黑色顯示)最遠的一個。從每個候選采樣點到最接近的樣本的距離由相關聯的線和圓圈表示：注意在灰色或紅色圓圈內部沒有其他樣本。在創建所有候選采樣點并測量距離之后，最佳候選采樣點成為新樣本，并且丟棄剩余候選采樣點。

▼代碼如下所示：

function sample() {

varbestCandidate, bestDistance = 0;

for(var i = 0; i < numCandidates; ++i) {

var c = [Math.random() * width, Math.random() * height],

d = distance(findClosest(samples, c), c);

if (d > bestDistance) {

bestDistance = d;

bestCandidate = c;

}

}

return bestCandidate;

}

正如我解釋了上面的算法，我會讓代碼獨立出來。(另外，這篇文章的目的是讓你通過可視化學習代碼)。但我會明確一些細節：

其中numCandidates表示一次生成的候選采樣點個數。這個參數讓你以質量換取速度。numCandidates越小，算法運行速度越快。相反，numCandidates越大，算法運行速度越慢，但是采樣質量越高。

▼distance函數是簡單幾何：

function distance(a, b) {

vardx = a[0] - b[0],

dy = a[1] - b[1];

return Math.sqrt(dx * dx + dy * dy);

}

如果你想的話，在這里可以忽略開平方(sqrt)，因為它是一個單調函數，并且，它不改變最佳候選采樣點的結果。

findClosest函數返回距離當前候選采樣點最近的采樣點。我們可以使用暴力搜索來實現，即對每一個現有的采樣點進行迭代。或者，可以讓搜索加速，如利用四叉樹搜索算法。暴力搜索實現簡單，但非常慢(時間復雜度太高)。而加速方式要快得多，但需要做更多的工作來實現。

談到權衡——在決定是否使用一個算法，我們不是憑空評估它，而是將其與其他方法進行比較。作為一個實際問題，權衡實施的復雜性：需要多久來實現、維護難度，對于衡量它的性能和質量是十分有用的。

▼最簡單的替代方法是均勻隨機采樣——

function sample() {

return [random() * width, random() * height];

}

它看起來是這樣的：

統一隨機是相當糟糕的。存在嚴重的欠采樣和過采樣：許多樣本點擁擠在一起，甚至重疊，導致大的空區域(當每次采樣的候選采樣點的數量被設置為1時，均勻隨機采樣也代表最佳候選算法的質量的下限)。

除了通過采樣點的分布規律來鑒別采樣質量，我們還可以嘗試通過根據最接近的樣本的顏色對圖像著色來在不同的采樣策略下模擬視覺。這實際上是采樣點的Voronoi圖，其中每個單元由相關樣品著色。

通過6667個均勻隨機采樣后的《星夜》看起來是怎樣的?

這種方法的弊端也很明顯。采樣點分布不均導致每個單位在尺寸大小上變化很大，和預期的不均勻采樣點分布一樣。細節丟失嚴重是因為密集采樣點(小單元)沒有充分利用起來。同時，稀疏采樣點(大單元)通過夸大稀有色彩(例如左下角的粉紅色)引入了噪音。

現在來看看最佳候選采樣：

好多了!雖然仍然隨機放置，但單元的大小更一致。盡管樣品的數量(6667)保持不變，但由于它們均勻分布，保留了更多的細節和引入了更少的噪聲。如果你瞇著眼睛，幾乎可以弄清楚原來的筆觸。

我們可以使用Voronoi圖來更直觀地研究樣本分布，通過根據其面積給每個單元上色。較暗的單元較大，表示稀疏采樣; 較淺的單元較小，表明密集采樣。最佳圖案具有幾乎均勻的顏色，同時保持不規則的采樣位置。(顯示單元面積分布的直方圖也是很好的，但是Voronoi具有同時顯示采樣位置的優點)。

這是同樣的6667個采樣點的不均勻隨機采樣：

黑點是采樣點之間的大空隙，可能是由于欠采樣導致的視覺局部缺陷。相同數量的最佳候選樣品在單元面積中表現出小得多的變化，并且因此著色更一致：

我們能做得比最佳候選算法更好嗎?是的! 我們不僅可以用不同的算法產生更好的樣本分布，而且這種算法更快(線性時間)。它至少像最佳候選算法一樣容易實現。這種算法甚至可以擴展到任意維度。

這個奇跡叫做Bridson的泊松盤采樣算法，它看起來像這樣：

該算法的功能明顯不同于其他兩個——它充分利用現有采樣點逐步生成新的采樣點，而不是在整個采樣區域隨機生成新的采樣點。這使其進展具有準生物學外觀，如在培養皿中分裂的細胞。注意，也沒有采樣點彼此太接近;這是定義由算法實施的泊松盤分布的最小距離約束。

這就是它的工作原理：

紅點表示“活躍”采樣點。在每次迭代中，從所有活躍采樣點的集合中隨機選擇一個。然后，在圍繞所選采樣點的環內隨機生成一些數量的候選采樣點(用空心黑點表示)。環從半徑r延伸到2r，其中r是樣本之間的最小允許距離。

來自現有采樣點的距離r內的候選采樣點被拒絕;這個“禁止區”以灰色顯示，用黑線連接將被拒絕的候選采樣點和附近的現有采樣點。網格加速每個候選采樣點的距離檢查。網格尺寸r /√2確保每個單元可以包含至多一個采樣點，并且僅需要檢查固定數量的相鄰單元。

如果候選采樣點是可以接受的，它被添加作為一個新的采樣點，然后隨機選擇一個新的活躍采樣點。如果沒有一個候選采樣點是可以接受的，所選擇的活躍采樣點被標記為無效(顏色從紅色變為黑色)。當沒有采樣點保持活躍時，該算法終止。

面積用著色表示的Voronoi圖顯示了泊松盤采樣算法相對于最佳候選算法的改進，沒有深藍色或淺黃色細胞：

泊松盤采樣下的《星夜》最大地保留了細節和引入了最少的噪音。它讓人想起美麗的羅馬馬賽克：

現在，你已經看到了一些例子，讓我們簡要地思考一下為什么要把算法可視化。

▼娛樂

我發現可視化的算法有無窮的魅力，甚至令人著迷。特別是在涉及隨機性時。雖然這看似是一個牽強的理由，但不要低估了快樂的價值!此外，盡管這些可視化甚至在不理解基礎算法的情況下也可以參與，但是掌握算法的重要性可以給出更深的理解。

▼教學

你發現代碼或動畫更有幫助嗎?偽代碼( 不能編譯的代碼的委婉語)怎么樣? 雖然形式描述在明確的文檔中有它的位置，可視化可以使直觀的理解更容易。

▼調試

你有沒有實現基于形式描述的算法? 可能很難! 能夠看到你的代碼在做什么可以提高生產力。 可視化不能取代測試需求，但測試主要用于檢測故障而不是解釋它。即使輸出看起來正確，可視化還可以在實現過程中發現意外的表現(參看Bret Victor的《可學習的編程》和為了優秀的相關工作的《發明原理》)。

▼學習

即使你只是想為自己學習，可視化會是一個很好的方式來得到深刻的理解。教學是最有效的學習方法之一，實現可視化就像教自己。我發現看到它，而不是熟記小而容易忘記細節的代碼，更容易直觀地記住一個算法。

洗牌

洗牌是隨機重新排列一組元素的過程。例如，你可以在打牌之前洗牌。一個好的洗牌算法是無偏的，其中每個排序都有相同的可能性。

Fisher-Yates shuffle是一個最佳的洗牌算法。 它不僅是無偏的，而且在線性時間內運行，使用恒定的空間，并且易于實現。

▼代碼如下——

function shuffle(array) {

varn = array.length, t, i;

while (n) {

i= Math.random() * n-- | 0; // 0 ≤ i < n

t= array[n];

array[n] = array[i];

array[i] = t;

}

return array;

}

以上是代碼，下面是一個可視化的解釋：

每一條線代表一個數字，數字小向左傾斜，數字大就向右傾斜。(請注意，你可以對一組任何東西進行洗牌，不只是數字，但這種可視化編碼對于顯示元素的順序很管用。它的靈感來自于Robert Sedgwick的《用C語言實現的算法》中的排序可視化。

該算法把數組劃分為兩個部分，右半邊是已洗牌區域(用黑色表示)，左半邊是待洗牌區域(用灰色表示)。每一步從左邊的待洗牌區域隨機選擇一個元素并將其移動到右側，已洗牌區域元素數量擴大了1個。左半邊的初始順序不必保留，這樣給已洗牌區域的新元素提供了空間，該算法可以簡單地講元素交換到位。最終所有的元素都被洗牌，算法終止。

如果Fisher–Yates是一個很好的算法，那么一個不好的算法是什么樣的?

▼這是一個——

//不要這么做!

function shuffle(array) {

return array.sort(function(a, b) {

return Math.random() - .5; // ?_?

});

}

這種方法利用排序通過指定隨機比較器函數來洗牌。比較器定義元素的順序。它使用參數a和b (要比較的數組中的兩個元素)，如果a小于b，則返回小于零的值，如果a大于b，則返回大于零的值，如果a和b相等，則返回0。比較器在排序期間重復調用。

如果不給array.sort指定一個比較器，元素按照字典序列排序。

在這里，比較器返回一個在-0.5和+0.5之間的隨機數。假設這定義了一個隨機順序，那么排序會隨機地混雜元素并實施好的洗牌。

不幸的是，這個假設是有缺陷的。隨機成對順序(對于任何兩個元素)不會為一組元素建立隨機順序。比較器必須遵守傳遞性：如果a> b和b> c，則a> c。但隨機比較器返回一個隨機值，違反了傳遞性，并導致array.sort的行為是未定義的!可能你會有運氣，也可能沒有。

它怎么不好呢?我們可以通過可視化輸出來試著回答這個問題：

該算法不好的另一個原因是排序需要O(n lg n)時間，使得它顯著地慢于只需要O(n)時間的Fisher-Yates算法。但是速度缺陷比偏差缺陷小。

這可能看起來是隨機的，因此你可能會得出結論，隨機比較器洗牌足夠好了，并不再關注偏差，看作是迂腐的。但看起來可能會誤導!有許多對人眼來說看起來是隨機的，但實際上是非隨機的。

這種欺騙表明可視化不是一個魔術棒。算法的單次運行顯示不能有效地評估其隨機性的質量。我們必須仔細設計一個可視化來解決手頭的具體問題：算法的偏差是什么?

為了顯示偏差，我們必須首先定義它。一個定義是基于在洗牌之后索引i處的數組元素將在洗牌之后處于索引j的概率。如果算法是無偏的，則每個元素在洗牌結束后出現在每個索引處的概率相等，因此所有i和j的概率相同：1 / n，其中n是元素的數量。

分析計算這些概率是困難的，因為它取決于知道使用的確切排序算法。但是根據經驗計算是很容易的：我們簡單地洗牌數千次，并計數索引j處元素i的出現次數。該概率矩陣的有效顯示是矩陣圖：

矩陣的列(水平位置)表示在洗牌之前的元素的索引，而行(垂直位置)表示洗牌之后的元素的索引。概率用顏色編碼：綠色單元表示正偏差，其中元素出現地比我們對無偏差算法的預期更頻繁;同樣紅色單元表示負偏差，其發生頻率低于預期。

如上所示，Chrome中的隨機比較器洗牌結果是令人驚訝的是平庸。部分陣列僅弱偏置。然而，它在對角線下方表現出強的正偏置，這表示將元素從索引i推到i + 1或i + 2的趨勢。第一行、中間行和最后一行也有奇怪的行為，這可能是Chrome使用“三中值”的快速排序的結果。

無偏的Fisher–Yates算法看上去是這樣的：

除了由于經驗測量的少量噪聲之外，在該矩陣中沒有可見的規律。(如果需要，可以通過進行額外的測量來降低噪聲。)

隨機比較器洗牌的行為在很大程度上取決于瀏覽器。不同的瀏覽器使用不同的排序算法，并且不同的排序算法與(破壞了的)隨機比較器表現非常不同。這里是隨機比較器在Firefox上洗牌的結果：

這是非常失偏的!所得到的數組通常幾乎沒有洗過牌，如該矩陣中的強綠色對角線所示。這并不意味著Chrome的排序是比Firefox的“更好”，它只是意味著不應該使用隨機比較器洗牌。隨機比較器從根本上被破壞了。

排序

排序是洗牌的逆過程——它從無序創建順序，反之亦然。這使得排序成為更困難的問題，要為不同的權衡和約束設計各種解決方案。

最知名的排序算法之一是快速排序。

Quicksort首先通過選擇一個基準將數組分成兩個部分。 左半部包含所有小于基準的元素，而右半部包含大于基準的所有元素。在數組分區后，快速排序在左右兩部分內遞歸。當每個部分只包含一個元素時，遞歸停止。

分區操作使得只在數組的活動部分上進行單一操作。類似于Fisher-Yates通過交換元素遞增地建立洗牌區，分區操作遞增地構建子陣列的較小(左)和較大(右)部分。當每個元素被訪問時，如果它小于基準，它被交換到較小部分; 如果它大于基準，則分區操作移動到下一個元素。

▼代碼如下所示——

function quicksort(array, left, right) {

if(left < right - 1) {

var pivot = left + right >> 1;

pivot = partition(array, left, right, pivot);

quicksort(array, left, pivot);

quicksort(array, pivot + 1, right);

}

}

function partition(array, left, right,pivot) {

varpivotValue = array[pivot];

swap(array, pivot, --right);

for(var i = left; i < right; ++i) {

if (array[i] < pivotValue) {

swap(array, i, left++);

}

}

swap(array, left, right);

return left;

}

快速排序有很多版本。上面顯示的是最簡單也是速度最慢的一個。這種變化對于教學是有用的，但是在實踐中，為了得到更好的性能應用了更復雜的實現方法。

常見的改進是“三中值”樞軸選擇，其中第一，中間和最后元素的中值被用作基準。這傾向于選擇更接近真實中值的基準，導致類似大小的左半部分和右半部分以及遞歸層數更少。另一個優化是對于數組的小部分來說，從快速排序切換到插入排序，由于函數調用的開銷問題這可以更快。

一個特別聰明的變化是Yaroslavskiy的雙基準快速排序，它將數組分為三個部分，而不是兩個。這是Java和Dart中的默認排序算法。

上面的排序和洗牌動畫有不錯的屬性，那就是時間映射到時間：我們可以簡單地觀察算法如何進行。但是雖然直觀，動畫也可以讓人在看的時候感到沮喪，特別是如果我們想關注偶然的、奇怪的算法的行為。動畫也嚴重依賴我們的記憶來觀察行為模式。雖然通過控制以暫停和擦洗時間來改進動畫，但是同時展示一切的靜態顯示甚至可以更有效。眼睛掃描比手動要快。

將動畫轉換為靜態顯示的一種簡單方法是從動畫中選擇關鍵幀，并按順序顯示，如同漫畫一樣。如果我們在關鍵幀之間刪除冗余信息，我們會更有效地使用空間。更密集的顯示可能需要更多的研究來理解，但是可以更快地掃描，因為眼睛移動較少。

下面，每一行顯示遞歸之前的數組的狀態。第一行是數組的初始狀態，第二行是第一次分區操作之后的數組，第三行是第一個分區的左右部分再次被分區之后的數組等等。實際上，這是廣度優先快速排序，其中左右兩側的分區操作并行進行。

與之前一樣，每個分區操作的基準以紅色突出顯示。請注意，在下一級遞歸處，基準將變為灰色：分區操作完成后，關聯的基準處于其最終的排序位置。顯示的總深度是遞歸的最大深度，給出了快速排序執行如何有效的感覺。它在很大程度上取決于輸入和基準選擇。

快速排序的另一個靜態顯示，密度較小但可能更容易讀，將每個元素表示為彩色線，并顯示每個順序交換。(這種形式是受到Aldo Cortesi的排序可視化的啟發。)更小的值顏色更輕，更大的值顏色更深。

現在已經看到了同一算法的三種不同的視覺展示：動畫、稠密靜態展示和稀疏靜態展示。每種形式都有各自的優缺點。動畫看起來有趣，但靜態的可視化允許仔細檢查，而不用著急。稀疏展示可能更容易理解，但密集展示除了顯示細節之外，還顯示算法行為的“宏觀”視圖。

在我們繼續下去之前，讓我們將快速排序與另一個眾所周知的排序算法——歸并排序進行對比。

▼下列為歸并排序的代碼——

function mergesort(array) {

varn = array.length, a0 = array, a1 = new Array(n);

for(var m = 1; m < n; m <<= 1) {

for (var i = 0; i < n; i += m << 1) {

var left = i,

right = Math.min(i + m, n),

end = Math.min(i + (m << 1), n);

merge(a0, a1, left, right, end);

}

i= a0, a0 = a1, a1 = i;

}

if(array === a1) {

for (var i = 0; i < n; ++i) {

array[i] = a0[i];

}

}

}

function merge(a0, a1, left, right, end) {

for(var i0 = left, i1 = right; left < end; ++left) {

if (i0 < right && (i1 >= end || a0[i0] <= a0[i1])) {

a1[left] = a0[i0++];

}else {

a1[left] = a0[i1++];

}

}

}

下面是相關的動畫展示：

正如你可能從代碼或動畫中推測的，歸并排序采用了一種與快速排序非常不同的排序方法。快速排序通過執行交換就地運行，與快速排序不同，歸并排序需要額外的數組副本。這個額外的空間用于歸并排序的子數組，把來自子數組的每對元素組合在一起，同時保持順序。由于歸并排序運行副本而不是交換，因此我們必須相應地修改動畫(或有誤導讀者的風險)。

歸并排序自下而上進行。最初，它合并大小為1的子數組，因為它們經過了排序。每個相鄰的子數組：首先，只是一對元素，使用額外的數組合并為大小為2的排序子數組。然后，將大小為2的每個相鄰排序子數組合并成大小為4的排序子數組。每次遍歷整個數組后，歸并排序將排序子數組的大小加倍：8，16，等等。最終，這個加倍合并了整個數組，算法終止。

因為歸并排序在數組上執行重復遍歷而不是像快速排序那樣遞歸，并且因為每次遍歷使排序的子數組的大小加倍，而不考慮輸入，所以更容易設計成靜態展示。我們只需在每次合并后顯示數組的狀態。

讓我們再花一點時間來想想我們所看到的。這里的目標是研究算法的行為而不是特定的數據集。但仍然有數據，這是必然的，因為數據是從算法的執行而導出的。這意味著我們可以使用派生數據的類型來將算法可視化分類。

▼第0級/黑盒

最簡單的類，只顯示輸出。不解釋算法的操作，但它仍然可以驗證正確性。通過將算法視為黑盒，可以更容易地比較不同算法的輸出。黑盒可視化還可以與更深入的輸出分析結合，例如上面顯示的隨機偏移矩陣圖。

▼第1級/灰盒

許多算法(雖然不是全部)增量地構建輸出。隨著它的進程，通過可視化過程中間的輸出，開始看到算法是如何工作的。這解釋了更多而不必引入新的抽象概念，因為過程中間和最終輸出共享相同的結構。然而，這種類型的可視化會產生比它可以回答的更多的問題，因為它沒有解釋為什么算法做它要做的事。

▼第2級/白盒

為了回答“為什么”這個問題，白盒可視化暴露算法的內部狀態以及其中間過程輸出。這種類型有最大的潛力來解釋，但也對讀者是最大的負擔，因為內部狀態的意義和目的必須清楚地描述。這里有一個風險，額外的復雜性會壓垮讀者;分層信息可以使圖形更容易獲得。最后，由于內部狀態高度依賴于特定算法，這種類型的可視化通常不適合于比較算法。

還有實現算法可視化的實際問題。通常不能只是運行代碼;必須有辦法捕獲它以便可視化(查看本文的源代碼示例)。甚至可能需要與可視化交叉執行，這對于捕獲遞歸算法的堆棧狀態尤其具有挑戰性。語言解析器如Esprima可以通過代碼檢測方便地實現算法可視化，將執行代碼與可視化代碼完全分離。

迷宮的生成

最后一個問題，我們會看下的是迷宮生成。本節中的所有算法生成二維矩形網格的生成樹。這意味著沒有循環，并且存在從左下角的根到迷宮中的每個其他單元的唯一路徑。

我為如此深奧的主題而感到歉意。我不知道為什么這些算法是有用的，除了簡單的游戲，可能是關于電氣網絡。但即使如此，它們從可視化視角看也很迷人，因為它們以非常不同的方式解決了同樣的有高度約束的問題。

觀看它們真有趣。

隨機遍歷算法初始化左下角的迷宮的第一個單元。該算法然后跟蹤迷宮可以擴展的所有可能的方式(以紅色標示)。在每個步驟，隨機挑選這些可能的擴展中的一個，只要這不重新連接它與另一個部分的迷宮，該迷宮就會延伸擴展。

像Bridon的泊松盤采樣算法一樣，隨機遍歷保持前沿，并從邊界中隨機選擇進行擴展。因此，兩種算法似乎都像真菌一樣有機地生長。

隨機深度優先遍歷遵循一個非常不同的模式：

不是每次都選擇一個新的隨機通道，該算法總是在隨機方向上延伸最深的通道，一個最長的回到根的通道。因此，隨機深度優先遍歷分支，僅當當前路徑是個死結時，進入迷宮的較早時的分支。要繼續，它會回溯，直到它可以開始一個新的分支。這種蛇狀的探索導致迷宮帶有明顯更少的分支和更長的蜿蜒通道。

Prim的算法構造最小生成樹，具有加權邊緣的圖的生成樹具有最低的總權重。 該算法可以用于通過隨機初始化邊緣權重來構建隨機生成樹：

在每個步驟中，Prim的算法使用連接到現有迷宮的最低加權邊緣(潛在方向)擴展迷宮。如果該邊緣將形成環路，則其被丟棄，然后考慮次最低加權邊緣。

Prim的算法通常使用堆來實現，這是用于對元素進行優先級排序的有效數據結構。 當一個新的單元格加入迷宮時，連接的邊緣(以紅色標示)被添加到堆。盡管邊以任意順序添加，堆允許快速除去最低加權邊。

最后，這是一個最不尋常的例子：

Wilson的算法使用循環擦除隨機游走來生成統一的生成樹，是所有可能的生成樹的無偏差樣本。我們看到的其他迷宮生成算法缺乏這個美麗的數學屬性。

該算法用任意起始單元初始化迷宮。然后，新的單元格被加入迷宮，啟動隨機游走(用紅色標示)。繼續隨機游走，直到它重新連接到現有的迷宮(用白色標示)。然而，如果隨機游走本身相交，則在隨機游走繼續之前擦除所得到的循環。

最初，算法看著可能令人沮喪地慢，因為早期隨機游走不可能與小的現有迷宮重新連接。隨著迷宮增長，隨機游走變得更可能與迷宮碰撞，并且算法加速顯著。

這四種迷宮生成算法的工作方式截然不同。然而，當動畫結束時，所得到的迷宮彼此件難以區分。動畫可用于顯示算法如何工作，但無法顯示生成的樹結構。

一種顯示結構，而不是過程的方法是用顏色填充迷宮：

顏色編碼樹深度——回到在左下角的根的路徑的長度。隨著越深入樹，顏色標度循環;當一個深路徑循環回鄰近一個淺路徑時，這偶爾會誤導，但更高的對比度允許更好的局部結構的分化。(這不是一個傳統的彩虹色標，名義上被認為有害，但立方體的彩虹具有改善的感知性能的能力。)

我們可以通過減去墻，進一步強調迷宮的結構，減少視覺噪聲。下面的圖中，每個像素表示通過迷宮的路徑。如上所述，路徑通過深度著色，隨著時間的推移，顏色像潮水一樣更深入迷宮。

顏色的同心圓，像領帶染色襯衫，揭示隨機遍歷產生許多分支路徑。然而，每條路徑的形狀不是特別有趣，因為它往往以直線回到根。因為隨機遍歷通過從邊界隨機采集來擴展迷宮，路徑從來沒有被給予很多蜿蜒的自由 - 它們最終與增長的邊界碰撞并且由于對循環的限制而終止。

另一方面，隨機深度優先遍歷都是關于蜿蜒的：

這個動畫以之前那個50倍的速度進行。這種加速是必要的，因為由于分支有限，隨機深度優先遍歷迷宮比隨機遍歷迷宮深得多。可以看到，在任何特定深度的活動分支通常只有一個，很少有多個。

下面，用隨機圖演示Prim的算法：

這更有趣!同時擴展的小花的顏色顯示基本的分支，并且有比隨機遍歷更復雜的全局結構。

Wilson的算法盡管操作很不同，卻似乎產生了非常相似的結果：

只是因為它們看起來相同并不意味著它們相同。盡管外觀上一樣，Prim的算法在隨機加權圖不生成統一的生成樹(據我所知，證明這是我的專業領域之外)。可視化有時會由于人為錯誤而會誤導。早期版本的Prim的顏色洪水有一個錯誤，顏色標度旋轉的速度是預期的兩倍;這表明Prim和Wilson的算法產生了非常不同的樹，而事實上它們看起來相似多于差異。

由于這些迷宮是生成樹，也可以使用專門的樹來可視化地顯示結構。為了說明迷宮和樹之間的對偶性，這里由Wilson的算法生成的迷宮的通道(以白色標示)逐漸變換成整潔的樹布局。與其他動畫一樣，它從深度開始，從根開始進一步擴展到葉子：

為了進行比較，我們再來看看隨機深度優先遍歷產生的擁有長通道和小分枝的樹。

兩棵樹具有相同數量的節點(3239)并且被縮放以適合相同區域(960×500個像素)。這隱藏了一個重要的區別：在這個尺寸上，隨機深度優先遍歷通常產生比Wilson的算法深兩到五倍的樹。上面的樹的深度分別為315和1338。在用于顏色洪水的更大的480000節點的迷宮中，隨機深度優先遍歷產生的樹深10到20倍!

利用視覺來思考

本文重點研究算法。然而，這里討論的技術適用于更廣泛的問題空間：數學公式、動態系統、過程等。基本上，任何需要理解代碼的地方。

那么，

——為什么要可視化算法呢?為什么要可視化一些東西?

——利用人的視覺系統，可以提高理解。或者更簡單地說，利用視覺去思考。

來源：https://bost.ocks.org/mike/algorithms/

　 作者 |Mike Bostock

翻譯|黃念

校對|馮琛 姚佳靈

選文 | 吳佳樂

素材來源 | bost.ocks.org

　　 注：本稿件摘自數據觀入駐自媒體-大數據文摘，轉載請注明來源，百度搜索“數據觀”獲取更多大數據資訊。

責任編輯：王超