摘要：所謂深度優(yōu)先算法，百科的解答是這樣的深度優(yōu)先搜索算法，簡(jiǎn)稱是搜索算法的一種。是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。

所謂深度優(yōu)先算法，百科的解答是這樣的

深度優(yōu)先搜索算法（Depth-First-Search），簡(jiǎn)稱DFS,是搜索算法的一種。是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。當(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)為止。屬于盲目搜索。

通俗的說(shuō)，就是足夠“深”的遍歷樹(shù)的所有節(jié)點(diǎn)分支并且遍歷過(guò)的節(jié)點(diǎn)不會(huì)再去訪問(wèn)，很適合做網(wǎng)絡(luò)爬蟲(chóng)，你懂得^ ^

而迷宮問(wèn)題也是數(shù)據(jù)結(jié)構(gòu)里面一道經(jīng)典的問(wèn)題了，首先我們先用矩陣創(chuàng)建一個(gè)迷宮；

const arr = [
        [0,0,0,1,0],
        [0,1,1,1,0],
        [0,1,0,0,0],
        [0,0,0,1,0],
        [0,1,1,1,0]
    ];

其中數(shù)字1代表墻壁，數(shù)字0代表路，最左上角代表入口，最右下角代表出口，這里我們不考慮“死路”的情況

const arr = [
    [0,0,0,1,0],
    [0,1,1,1,0],
    [0,1,0,0,0],
    [0,0,0,1,0],
    [0,1,1,1,0]
];//創(chuàng)建迷宮

const pathX = [1,-1,0,0];//創(chuàng)建一個(gè)數(shù)組代表上下左右，在advance這個(gè)函數(shù)會(huì)用到
const pathY = [0,0,-1,1];//同上，區(qū)別在于矩陣的行和列
let _arrLength = arr.length-1;
let _arrElementLength = arr[0].length-1;
let i=0,j=0;
(function(){
    console.time("time")//用于測(cè)試運(yùn)算時(shí)間

    arr[0][0] = 3;//數(shù)字3代表已經(jīng)走過(guò)的路，一開(kāi)始默認(rèn)從入口進(jìn)入

    function matrix(i,j){

        let k,newi,newj;

        for(k = 0;k<4;k++){ //上下左右總共四個(gè)方向

            if (advance(i,j,k)) {   
                /*
                通過(guò)advance函數(shù)的判斷返回一個(gè)可走的路的點(diǎn)
                */
                newi = i + pathX[k];
                newj = j + pathY[k];   
                
                arr[newi][newj] = 3;//將這個(gè)點(diǎn)定義為已走過(guò)的點(diǎn)
                
                /*
                判斷此時(shí)是否已經(jīng)到了終點(diǎn)如果沒(méi)有則遞歸
                */
                if (newi == _arrLength && newj == _arrElementLength) {
                    end()
                } else {   
                    matrix(newi,newj);   
                }   
            }
        }
        arr[i][j] = 2

    }
    matrix(0,0)

    function advance(i,j,k){
        var bool = true;
         /*
        每走一步路就判斷其上下左右是否還有路可走
        */
        i += pathX[k];
        j += pathY[k];
        /*
        判斷臨界范圍，保證在迷宮范圍內(nèi)
        */
        if(i<0||i>_arrLength||j<0||j>_arrElementLength){
            bool = false;
        }else if(arr[i][j]!=0){
            bool = false;
        }
        return bool;
    }


    /*
    負(fù)責(zé)輸出結(jié)果
    */
    function end(){
        let i,j,newArr=[];
        for (i = 0; i < _arrLength+1; i++) {   
            for (j = 0; j < _arrLength+1; j++) {   
                if (arr[i][j] == 3) { 
                    newArr.push("V");  
                } else {   
                    newArr.push("*");   
                }
            }   
        }
        /*
        下面這段代碼只是為了能夠在控制臺(tái)看得更直觀，可無(wú)，因?yàn)閷?xiě)得有點(diǎn)笨拙
        */
        newArr.splice(0,0,"")
        newArr.splice(6,0,"
");
        newArr.splice(12,0,"
");
        newArr.splice(18,0,"
");
        newArr.splice(24,0,"
");
        console.log(newArr.join(" "));
    }
    console.timeEnd("time")
})()

最終的路線圖如下