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

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

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

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

想必你肯定玩過問答類的性格測試游戲，游戲規(guī)則非常簡單，按照心中所想回答問題即可。回答完一個問題后會跳轉(zhuǎn)到另外一個問題，不同的回答可能進(jìn)入不同的分支?；卮鹜晁袉栴}后會給出一個關(guān)于你性格的解答，如下圖。

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

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

下面先來POST一些概念。

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

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

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

如上圖，按DFS的方式以A為起點(diǎn)去遍歷的話，遍歷順序?yàn)椋?/p>

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

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

示例代碼

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

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

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

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

測試結(jié)果

在線示例

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

1.棧的使用

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

2.環(huán)路的判斷

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

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

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

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

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

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

上面我們只有幾個節(jié)點(diǎn)，每個節(jié)點(diǎn)只有2個出度，因此運(yùn)算起來很快。如果增加到12個節(jié)點(diǎn)呢，每個節(jié)點(diǎn)4個出度呢？

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

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

另一方面，我們討論了DFS算法的時間復(fù)雜度，當(dāng)圖的頂點(diǎn)數(shù)增加到一定程度時，運(yùn)算量暴漲，也因此拋出了一個性能的問題。在看似簡單的實(shí)現(xiàn)中，我們其實(shí)要注意處理好細(xì)節(jié)，畢竟，放大到1億次運(yùn)算，都不是小事！

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