搜索

搜索算法实际上是根据初始条件和扩展规则构造搜索树寻找符合目标节点的过程。所有的搜索算法本质上看都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。 其实，在这样的思考过程中，我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。

一、广度优先搜索（Breadth-First-Search, BFS）

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记录正在访问的顶点的下一层顶点

例题：https://leetcode-cn.com/problems/word-ladder/

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    let wordMap = new Map();
    // 根据通用状态生成邻接关系
    for (let item of wordList) {
        for (let index in item) {
            index = parseInt(index)
            let key = item.substring(0, index) + '_' + item.substring(index + 1)
            if(wordMap.has(key)) {
                wordMap.get(key).push(item)
            }else{
                wordMap.set(key, [item])
            }
        }
    }
    // BFS辅助队列
    let Queue = [];
    Queue.push({word: beginWord, level: 1})
    // 访问序列
    let visited = new Map();
    // 队列非空
    while(Queue.length !== 0) {
        let node = Queue.shift();
        let nodeWord = node.word;
        let level = node.level;
        if(nodeWord === endWord) {
            return level;
        }
        // 判断每一层是否包含目标节点，如果没有，并且节点未被访问，则节点入队，标记为已读
        for(let i = 0; i < nodeWord.length; i++) {
            let key = nodeWord.substring(0, i) + '_' + nodeWord.substring(i + 1)
            let WordArr = wordMap.get(key);
            if(WordArr) {

            for(let word of WordArr) {
                if(word === endWord) {
                    return level + 1;
                }
                if(!visited.has(word)) {
                    visited.set(word,true)
                    Queue.push({
                        word:  word,
                        level: level + 1
                    })
                }
            }
            }
        }
    }
    return 0;
};

二、深度优先搜索（Depth-First-Search，DFS ）

深度优先搜索算法 是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

在树的遍历中，我们可以用 DFS 进行 前序遍历，中序遍历和后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯。这也是 DFS 和 BFS 之间最大的区别，BFS永远不会深入探索，除非它已经在当前层级访问了所有结点。

有两种实现 DFS 的方法。一种方法是进行递归，另一种是使用栈。

例题：https://leetcode-cn.com/problems/keys-and-rooms/

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let seen = new Array(rooms.length)
    seen[0] = true
    let stack = []
    stack.push(0);
    while(stack.length !== 0) {
        let node = stack.pop();
        for(let item of rooms[node]) {
            if(!seen[item]) {
                seen[item] = true;
                stack.push(item)
            }
        }
    }

    for(let i = 0; i<seen.length; i++) {
        if(!seen[i]) {
            return false;
        }
    }
    return true;
};