深度广度优先遍历

什么是深度/广度优先遍历?

• 深度优先遍历：尽可能深的搜索图的分支。

• 广度优先遍历：先访问离根节点最近的节点。

深度优先遍历算法口诀

• 访问根节点。

• 对根节点的没有访问过的相邻节点挨个进行深度的优先遍历。

深度优先遍历练习

数据

const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
};

module.exports = graph;

深度优先遍历代码

const graph = require('./graph');

const visited = new Set();
const dfs = (n) => {
    console.log(n);
    visited.add(n);
    graph[n].forEach(c => {
        if(!visited.has(c)){
            dfs(c);
        }
    });
};

dfs(2);

广度优先遍历口诀

• 新建一个队列，把根节点入队。

• 把队头出队并访问。

• 把队头没有访问过的相邻节点入队。

• 重复二三步直到队列为空。

广度优先遍历练习

广度优先遍历代码

const graph = require('./graph');

const visited = new Set();
visited.add(2);
const q = [2];
while (q.length) {
    const n = q.shift();
    console.log(n);
    graph[n].forEach(c => {
        if (!visited.has(c)) {
            q.push(c);
            visited.add(c);
        }
    });
}