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

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

隊列是先進先出，后進后出，常用的操作是取第一個元素（shift）、尾部加入一個元素（push）。

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

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

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

1進隊列 【1】

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

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

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

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

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

繼續(xù)一個個取出

到了最后，隊列清空，樹也遍歷了一次

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

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

問：1能不能到達5

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

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

每個節(jié)點分別用兩個數(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é)點隊列的子節(jié)點
    var count = 0
    var state = false//判斷是否結(jié)束循環(huán)
    while(!state){
        while(quene.length){//如果隊列不是空，從前面一個個取，并把他的子節(jié)點放在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++//隊列已經(jīng)空，說明這層的節(jié)點已經(jīng)全部檢索完，而且子節(jié)點也保存好了
        quene = [...temp]//隊列是子節(jié)點所有的元素集合,重復(fù)前面操作
        temp = []
    }
    return count
}
3.DFS
DFS著重于這個搜索的過程，一般以“染色”的形式配合棧來運行，也比較徹底。V8老生代的垃圾回收機制中的標記-清除也利用了DFS。我們定義三種顏色：黑白灰，白色是未處理過的，灰是已經(jīng)經(jīng)過了但沒有處理，黑色是已經(jīng)處理過了
還是前面那幅圖

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

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

我們可以看到，入棧的時候，從白色染灰色，出棧的時候，從灰色到黑色。整個過程中，染黑的順序類似于二叉樹的后序遍歷
v8的垃圾回收，將持有引用的變量留下，沒有引用的變量清除。因為如果持有引用，他們必然在全局的樹中被遍歷到。如果沒有引用，那這個變量必然永遠是白色，就會被清理
我們用對象來表示上面這棵樹：
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é)點的說明已經(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上面每一個節(jié)點都是黑色了。遍歷中間過程，每一個節(jié)點入棧的時候是灰色的，出棧的時候是黑色的。