摘要：隊(duì)列棧隊(duì)列是先進(jìn)先出，后進(jìn)后出，常用的操作是取第一個(gè)元素尾部加入一個(gè)元素。棧是后進(jìn)先出，就像一個(gè)垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的，出棧的時(shí)候是黑色的。

廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優(yōu)方法、組合等等。于是，我們不妨動(dòng)手試一下js版本怎么玩。

隊(duì)列是先進(jìn)先出，后進(jìn)后出，常用的操作是取第一個(gè)元素（shift）、尾部加入一個(gè)元素（push）。

棧是后進(jìn)先出，就像一個(gè)垃圾桶，后入的垃圾先被倒出來。常用的操作是，尾部加入元素（push），尾部取出元素（pop）

BFS是靠一個(gè)隊(duì)列來輔助運(yùn)行的。顧名思義，廣度搜索，就是對于一個(gè)樹形結(jié)構(gòu)，我們一層層節(jié)點(diǎn)去尋找目標(biāo)節(jié)點(diǎn)。

按照這個(gè)順序進(jìn)行廣度優(yōu)先遍歷，明顯是隊(duì)列可以完美配合整個(gè)過程：

1進(jìn)隊(duì)列 【1】

取出隊(duì)列第一個(gè)元素1，將1的子節(jié)點(diǎn)234按順序加入隊(duì)列后面 【2，3，4】

取出隊(duì)首元素2，將他的子節(jié)點(diǎn)按順序加入隊(duì)列 【3，4，5，6】

取出3，將子節(jié)點(diǎn)7加入 【4，5，6，7】

取出4，將子節(jié)點(diǎn)89加入【5，6，7，8，9】

取出5，沒有子節(jié)點(diǎn)，沒有什么干

繼續(xù)一個(gè)個(gè)取出

到了最后，隊(duì)列清空，樹也遍歷了一次

假設(shè)有幾個(gè)點(diǎn)，我們需要設(shè)計(jì)一個(gè)算法，判定兩個(gè)點(diǎn)有沒有相通

假設(shè)點(diǎn)12345是這樣的結(jié)構(gòu)：

問：1能不能到達(dá)5

顯然我們一眼看上去是不會到達(dá)的，如果是設(shè)計(jì)算法的話，怎么做呢？

我們把點(diǎn)之間的關(guān)系用一個(gè)矩陣表示，0表示不連接，n行m列的1表示點(diǎn)n通向點(diǎn)m

var map = [ 
[0,1,1,0,0],
[0,0,1,1,0],
[0,1,1,1,0],
[1,0,0,0,0],
[0,0,1,1,0]
]

function bfs(arr,start,end){
    var row = arr.length
    var quene = []
    var i = start
    var visited = {}//記錄遍歷順序
    var order = [] //記錄順序，給自己看的
    quene.push(i) //先把根節(jié)點(diǎn)加入
    while(quene.length){ //如果隊(duì)列沒有被清空，也就是還沒遍歷完畢
        for(var j = 0;j
1.2 樹的BFS舉例
舉個(gè)例子，3月24號今日頭條筆試題第二題的最少操作步數(shù)：
定義兩個(gè)字符串變量：s和m，再定義兩種操作，
第一種操作：
m = s;
s = s + s;
第二種操作：
s = s + m;
假設(shè)s, m初始化如下：
s = "a";
m = s;
求最小的操作步驟數(shù)，可以將s拼接到長度等于n
輸入一個(gè)整數(shù)n，表明我們需要得到s字符長度，0案例：
in:
6
out:
3
思路：利用廣度優(yōu)先搜索，假設(shè)左節(jié)點(diǎn)是操作1，右節(jié)點(diǎn)是操作2，這樣子就形成了操作樹。利用bfs的規(guī)則，把上層的父節(jié)點(diǎn)按順序加入隊(duì)列，然后從前面按順序移除，同時(shí)在隊(duì)列尾部加上移除的父節(jié)點(diǎn)的子節(jié)點(diǎn)。我這里，先把父節(jié)點(diǎn)拿出來對比，他的子節(jié)點(diǎn)放在temp，對比完了再把子節(jié)點(diǎn)追加上去

每個(gè)節(jié)點(diǎn)分別用兩個(gè)數(shù)記錄s，m。發(fā)現(xiàn)第一次兩種操作是一樣的，所以我就略去右邊的了
function bfs(n){
    if(n<2||n!==parseInt(n)||typeof n !=="number") return
    if(n==2) return 1
    var quene = [[2,1]]//從2開始
    var temp = []//存放父節(jié)點(diǎn)隊(duì)列的子節(jié)點(diǎn)
    var count = 0
    var state = false//判斷是否結(jié)束循環(huán)
    while(!state){
        while(quene.length){//如果隊(duì)列不是空，從前面一個(gè)個(gè)取，并把他的子節(jié)點(diǎn)放在temp
            var arr = quene.pop()
            if(arr[0]==n){//找到了直接結(jié)束
                state = true
                break
            }
                temp.push([arr[0]*2,arr[1]*2])
                temp.push([arr[0]+arr[1],arr[1]])
        }
        count++//隊(duì)列已經(jīng)空，說明這層的節(jié)點(diǎn)已經(jīng)全部檢索完，而且子節(jié)點(diǎn)也保存好了
        quene = [...temp]//隊(duì)列是子節(jié)點(diǎn)所有的元素集合,重復(fù)前面操作
        temp = []
    }
    return count
}
3.DFS
DFS著重于這個(gè)搜索的過程，一般以“染色”的形式配合棧來運(yùn)行，也比較徹底。V8老生代的垃圾回收機(jī)制中的標(biāo)記-清除也利用了DFS。我們定義三種顏色：黑白灰，白色是未處理過的，灰是已經(jīng)經(jīng)過了但沒有處理，黑色是已經(jīng)處理過了
還是前面那幅圖

我們用兩個(gè)數(shù)組，一個(gè)是棧，一個(gè)是保存我們遍歷順序的，數(shù)組的元素拿到的都是原對象樹的引用，是會改變原對象的節(jié)點(diǎn)顏色的

從根節(jié)點(diǎn)開始，把根節(jié)點(diǎn)1壓入棧，染成灰色 【1：灰】
發(fā)現(xiàn)1的白色子節(jié)點(diǎn)2，壓入棧染色【1：灰，2：灰】
發(fā)現(xiàn)2的白色子節(jié)點(diǎn)5，入棧染色【1：灰，2：灰，5：灰】
發(fā)現(xiàn)5沒有白色子節(jié)點(diǎn)，于是5已經(jīng)確認(rèn)是遍歷過的，5出棧染黑色【1：灰，2：灰】，【5：黑】
回溯2，發(fā)現(xiàn)2還有白色子節(jié)點(diǎn)6，6入棧染灰，發(fā)現(xiàn)6沒有子節(jié)點(diǎn)，6出棧染黑色，【1：灰，2：灰】，【5：黑，6：黑】；又發(fā)現(xiàn)2沒有白色子節(jié)點(diǎn)，2出棧染黑色【1：灰】，【5：黑，6：黑，2：黑】
2又回溯1，發(fā)現(xiàn)1還有白色子節(jié)點(diǎn)3，3入棧染灰【1：灰，3：灰】，【5：黑，6：黑，2：黑】
同樣的，7沒有白色子節(jié)點(diǎn)，7入棧直接出棧染黑，【1：灰，3：灰】，【5：黑，6：黑，2：黑，7：黑】；3沒有白色子節(jié)點(diǎn)【1：灰】出棧染黑，【5：黑，6：黑，2：黑，7：黑，3：黑】
到了4，【1：灰，4：灰】，他有白色子節(jié)點(diǎn)89，而89沒有白色子節(jié)點(diǎn)，所以89入棧又直接出棧了【1：灰，4：灰】，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑】
4這次就沒有白色子節(jié)點(diǎn)了，到他出棧染黑，【1：灰】，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑，4：黑】
回溯，發(fā)現(xiàn)1沒有白色子節(jié)點(diǎn)，最后1出棧染黑，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑，4：黑，1：黑】

我們可以看到，入棧的時(shí)候，從白色染灰色，出棧的時(shí)候，從灰色到黑色。整個(gè)過程中，染黑的順序類似于二叉樹的后序遍歷
v8的垃圾回收，將持有引用的變量留下，沒有引用的變量清除。因?yàn)槿绻钟幸茫麄儽厝辉谌值臉渲斜槐闅v到。如果沒有引用，那這個(gè)變量必然永遠(yuǎn)是白色，就會被清理
我們用對象來表示上面這棵樹：
var tree = {
    val: 1,
    children: [
        {val: 2,children: [{val:5,children:null,color:"white"},{val: 6,children:null,color:"white"}],color:"white"},
        {val: 3,children: [{val: 7,children:null,color:"white"}],color:"white"},
        {val: 4,children: [{val:8,children:null,color:"white"},{val: 9,children:null,color:"white"}],color:"white"}
    ],
    color: "white"
}
開始我們的DFS：
function dfs ( tree ) {
    var stack = []//記錄棧
    var order = []//記錄遍歷順序
    !function travel (node) {
        stack.push(node)//入棧
        node.color = "gray"
        console.log(node)
        if(!node.children) {//沒有子節(jié)點(diǎn)的說明已經(jīng)遍歷到底
            node.color = "black"
            console.log(node)
            stack.pop()
            order.push(node)
            return
        }
        var children = node.children    
        children.forEach(child=>{
            travel(child)
        })
        node.color = "black"
        stack.pop()//出棧
        order.push(node)
        console.log(node)
    }(tree)
    return order
}
過程用遞歸比較簡單，上面大部分代碼都是調(diào)試代碼，自己可以改一下測試其他的類似場景。遍歷完成后，tree上面每一個(gè)節(jié)點(diǎn)都是黑色了。遍歷中間過程，每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的，出棧的時(shí)候是黑色的。