深度优先搜索

1. 每次都争取沿着邻接点一路走到底,并进行访问 即没有邻接点为止
2. 往回走一个顶点, 看看有哪个邻接点没有访问过的
   1. 有就再次沿着一条路径走到底, 再往回走…
   2. 没有就再往回走…
3. 最后一定每个顶点都只会访问一次

实现方式

• 通常使用递归

function dfs(node) {
    console.log(node.value); // 首先访问当前节点的值
    node.children.forEach(child => {
        dfs(child); // 递归访问每个子节点
    });
}

• child::迭代实现深度优先搜索

实际应用

非常适合分治法 beused::分治法

function dfs(node, ...args){
    // 对参数进行一些决策
    if(...args){
        //🤔
    }
    let rst = []
    rst.push(dfs(subnode,...newArgs))
}