摘要：小結使用深度優先算法，我們能夠檢測性格測試游戲的邏輯正確性，相比以往課堂上的理論，在這里算是一個具體的應用場景吧。其實深度優先算法的應用面也很廣，遲早還會再碰面的。

在開始前想先說一下關于這個課題的感想——能學以致用是一件很快樂的事情。

深度優先算法（簡稱DFS），在大學的數據結構課本中有這一個章節，依稀記得另外一個叫廣度優先算法（簡稱BFS），在當時的我看來，它們都還只是理論。萬萬沒想到的是，在畢業后的兩年，我會接觸到它們，并寫下關于這個算法的應用文章，而契機是一個跟性格測試有關的游戲。

這個系列文章的重點，是如何利用DFS算法來檢測有向圖的回路，而具體的應用場景，就是性格測試。相比于純講理論，我更喜歡從實際應用出發，如果你對此感興趣，就請繼續看下去吧。

想必你肯定玩過問答類的性格測試游戲，游戲規則非常簡單，按照心中所想回答問題即可。回答完一個問題后會跳轉到另外一個問題，不同的回答可能進入不同的分支。回答完所有問題后會給出一個關于你性格的解答，如下圖。

問題就來了，這種性格測試游戲的模型其實是一張有向圖。一般而言，題目及答案都是作者設定好的，因此不會出現死循環，也就是環路。例如 1->2->4->1，就是一個死循環，玩家可能一直在第1、2、4這三道題一直循環，游戲不能結束。

如果游戲很復雜，有很多道題目，有可能會設計出死循環。那么像這種環路，我們能用程序檢測出來嗎？答案是肯定的。

下面先來POST一些概念。

摘自：百度百科 - 圖
在數學中，一個圖（Graph）是表示物件與物件之間的關系的數學對象，是圖論的基本研究。

摘自：百度百科 - 圖
如果給圖的每條邊規定一個方向，那么得到的圖稱為有向圖。

摘自：百度百科 - 深度優先搜索
深度優先搜索算法（Depth-First-Search），是搜索算法的一種。是沿著樹或圖的深度遍歷節點，盡可能深的搜索分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。

如上圖，按DFS的方式以A為起點去遍歷的話，遍歷順序為：

A-B-D-E-C-F-G

如果還有不明白的可以自行Google一下。

示例代碼

/**
 * 測試數據，1代表第一題，2代表第二題，-1代表結果A，-2代表結果B，以此類推
 * @type {Array}
 */
var testData = [
    [2, 3],
    [4, -3],
    [-1, -2],
    [1, -2]
];

/**
 * 遞歸測試，使用深度優先算法
 * @param  {Array}  data   測試數據
 * @param  {Number} qIndex 問題下標
 * @param  {Number} aIndex 答案下標
 * @param  {Array}  path   當前回答路徑，例如[1,2,4]代表1->2->4的回答順序
 */
function recurseTest(data, qIndex, aIndex, path) {
    var question = data[qIndex]; // 當前問題
    var answer = question[aIndex]; // 要遍歷的答案
    // 1.判斷是否跳轉到結果
    if (answer > 0) { // 跳轉到其他問題
        if (path.indexOf(answer) > -1) { // 邏輯錯誤，當前回答路徑已存在，死循環
            var result = path.concat([answer, "wrong"]).join(", ");
            showResult(result);
        } else { // 邏輯正確，繼續沿著這個答案遍歷下去
            path.push(answer);
            recurseTest(data, answer - 1, 0, path);
        }
    } else { // 跳轉到結果
        path.push(answer);
    }
    // 2.判斷是否最后一個答案
    if (aIndex === question.length - 1) { // 已經是當前這道題的最后一個答案，返回上層
        var result = path.concat(["true"]).join(", ");
        showResult(result);
        path.pop();
    } else if (aIndex < question.length - 1) { // 還有其他答案，使用下一個答案遍歷下去
        recurseTest(data, qIndex, aIndex + 1, path);
    }
}

/**
 * 顯示回答結果
 * @param  {String} content 內容
 */
function showResult(content) {
    console.log(content);
    if (typeof document !== "undefined") {
        var div = document.createElement("div");
        div.innerText = content;
        document.body.appendChild(div);
    }
}

// 測試一下
showResult("測試結果：");
recurseTest(testData, 0, 0, [1]);

測試結果

在線示例

https://jsfiddle.net/Vincent_...

1.棧的使用

上述代碼中的數組path，應該理解成一個棧，它記錄的是當前遞歸的回答順序，比如[1, 2, 4]，代表著，先回答第一題，再回答第二題，再回答第四題。

2.環路的判斷

假如下一個要移動到的問題的序號，存在于棧中，就代表出現了環路，例如[1, 2, 4, 1]，此時代表出現了死循環。

3.返回上層，遍歷下一條分支

這個時候就體現出棧的作用了，比如我們跑完了1->2->?的分支后，需要跑1->3->?的分支，即返回上層，則使2出棧，3入棧。

DFS算法的時間復雜度是：O(b^m) （b-分支系數，m-圖的最大深度）

因此可以看出如果分支系數越大（也就是每一題的答案越多），圖深度越大（題目的數量越多），時間復雜度就越高。

為此，我們可以來看看運行這個檢測的方法，花了多少時間，遞歸了多少次：

上面我們只有幾個節點，每個節點只有2個出度，因此運算起來很快。如果增加到12個節點呢，每個節點4個出度呢？

沒錯，是兩千多萬次遞歸，時間也來到了接近300ms，越多的頂點和邊將帶來更多的檢測時間，因此檢測過多的頂點和邊將帶來性能問題，這是使用深度優先算法來檢測的時候需要注意的。（之前就是因為一個游戲配了20道題，運行一下這個檢測方法，直接跑到崩潰。。。）

使用深度優先算法，我們能夠檢測性格測試游戲的邏輯正確性，相比以往課堂上的理論，在這里算是一個具體的應用場景吧。其實深度優先算法的應用面也很廣，遲早還會再碰面的。

另一方面，我們討論了DFS算法的時間復雜度，當圖的頂點數增加到一定程度時，運算量暴漲，也因此拋出了一個性能的問題。在看似簡單的實現中，我們其實要注意處理好細節，畢竟，放大到1億次運算，都不是小事！

最后，希望大家會喜歡這樣的文章吧。