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

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

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

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

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

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

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

下面先來(lái)POST一些概念。

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

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

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

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

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

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

示例代碼

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

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

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

測(cè)試結(jié)果

在線示例

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

1.棧的使用

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

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

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

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

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

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

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

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

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

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

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

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

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