第 5 题：介绍下深度优先遍历和广度优先遍历，如何实现？

[atheist1]

第五题问的是深度优先遍历和广度优先遍历，我是从dom节点的遍历来理解这个问题的

html代码

我将用深度优先遍历和广度优先遍历对这个dom树进行查找

深度优先遍历

---

深度优先遍历DFS 与树的先序遍历比较类似。
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

/*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList)
    }
  }
  return nodeList
}
let deepTraversal2 = (node) => {
    let nodes = []
    if (node !== null) {
      nodes.push(node)
      let children = node.children
      for (let i = 0; i < children.length; i++) {
        nodes = nodes.concat(deepTraversal2(children[i]))
      }
    }
    return nodes
  }
// 非递归
let deepTraversal3 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入当前处理的node
    stack.push(node)
    while (stack.length) {
      let item = stack.pop()
      let children = item.children
      nodes.push(item)
      // node = [] stack = [parent]
      // node = [parent] stack = [child3,child2,child1]
      // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
      // node = [parent, child1-1] stack = [child3,child2,child1-2]
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

输出结果

广度优先遍历

---

广度优先遍历 BFS
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

let widthTraversal2 = (node) => {
  let nodes = []
  let stack = []
  if (node) {
    stack.push(node)
    while (stack.length) {
      let item = stack.shift()
      let children = item.children
      nodes.push(item)
        // 队列，先进先出
        // nodes = [] stack = [parent]
        // nodes = [parent] stack = [child1,child2,child3]
        // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
        // nodes = [parent,child1,child2]
      for (let i = 0; i < children.length; i++) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

输出结果

ps

仅个人理解，如果有错欢迎大家指出批评，一起进步

[shiiiiiiji]

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？

---

2.14补充
对象的深拷贝

[sisterAn]

图

图是一种复杂的非线性结构，它由边（边Edge）和点（顶点Vertex）组成。一条边连接的两个点称为相邻顶点。

G = (V, E)

图分为：

• 有向图
• 无向图

本文探讨的是无向图

图的表示

图的表示一般有以下两种：

• 邻接矩阵：使用二维数组来表示点与点之间是否有边，如 arr[i][j] = 1表示节点 i 与节点 j 之间有边，arr[i][j] = 0表示节点 i 与节点 j 之间没有边
• 邻接表：邻接表是图的一种链式储存结构，这种结构类似树的子链表，对于图中的每一个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就是顶点Vi的邻接表，单链表一般由数组或字典结构表示。

创建图

下面声明图类，Vertex 用数组结构表示，Edge 用 map结构表示

function Graph() {
    this.vertices = [] // 顶点集合
    this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
    this.vertices.push(v)
    this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
    let vEdge = this.edges.get(v)
    vEdge.push(w)
    let wEdge = this.edges.get(w)
    wEdge.push(v)
    this.edges.set(v, vEdge)
    this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
    var s = ''
    for (var i=0; i<this.vertices.length; i++) {
        s += this.vertices[i] + ' -> '
        var neighors = this.edges.get(this.vertices[i])
        for (var j=0; j<neighors.length; j++) {
            s += neighors[j] + ' '
        }
        s += '\n'
    }
    return s
}

测试：

var graph = new Graph()
var vertices = [1, 2, 3, 4, 5]
for (var i=0; i<vertices.length; i++) {
    graph.addVertex(vertices[i])
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);

console.log(graph.toString())
// 1 -> 4 3 
// 2 -> 3 5 
// 3 -> 1 2 
// 4 -> 1 
// 5 -> 2

测试成功

图的遍历

两种遍历算法：

• 深度优先遍历
• 广度优先遍历

深度优先遍历（DFS）

深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。

简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。

DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。

注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。

步骤：

• 访问顶点v
• 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问
• 若此时途中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到所有顶点均被访问过为止

实现：

Graph.prototype.dfs = function() {
    var marked = []
    for (var i=0; i<this.vertices.length; i++) {
        if (!marked[this.vertices[i]]) {
            dfsVisit(this.vertices[i])
        }
    }
    
    function dfsVisit(u) {
        let edges = this.edges
        marked[u] = true
        console.log(u)
        var neighbors = edges.get(u)
        for (var i=0; i<neighbors.length; i++) {
            var w = neighbors[i]
            if (!marked[w]) {
                dfsVisit(w)
            }
        }
    }
}

测试：

graph.dfs()
// 1
// 4
// 3
// 2
// 5

测试成功

广度优先遍历（BFS）

广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS

BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层

步骤：

• 创建一个队列，并将开始节点放入队列中
• 若队列非空，则从队列中取出第一个节点，并检测它是否为目标节点
  • 若是目标节点，则结束搜寻，并返回结果
  • 若不是，则将它所有没有被检测过的字节点都加入队列中
• 若队列为空，表示图中并没有目标节点，则结束遍历

实现：

Graph.prototype.bfs = function(v) {
    var queue = [], marked = []
    marked[v] = true
    queue.push(v) // 添加到队尾
    while(queue.length > 0) {
        var s = queue.shift() // 从队首移除
        if (this.edges.has(s)) {
            console.log('visited vertex: ', s)
        }
        let neighbors = this.edges.get(s)
        for(let i=0;i<neighbors.length;i++) {
            var w = neighbors[i]
            if (!marked[w]) {
                marked[w] = true
                queue.push(w)
            }
        }
    }
}

测试：

graph.bfs(1)
// visited vertex:  1
// visited vertex:  4
// visited vertex:  3
// visited vertex:  2
// visited vertex:  5

测试成功

本文始发于我的博客：深度优先遍历与广度优先遍历

[kscript]

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？

2.14补充
对象的深拷贝

前端确实很少涉及算法。 这个我也只在做小游戏的时候有用到过

[vivatoviva]

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？

2.14补充
对象的深拷贝

Dom树的遍历

[caihg]

@atheist1
非递归版的 deepTraversal3 实际上是广度优先的

[Ray-56]

@caihg 我也是这样想的

[BaconZhang]

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？

2.14补充
对象的深拷贝

这其实是和公司的具体业务相关的，我们公司把在业务层背后抽象了一套树形结构的领域对象模型，整个项目里少不了折腾树的递归，这时候发现熟练掌握深度遍历和广度遍历就十分有用了。

[rccoder]

@atheist1 宽搜还是写 queue 吧，stack 歧义太严重了

[iamwelk]

这个字打错了吧

[MaxPeak]

写得非常好了，我之前也了解过这两个东西，@atheist1 ，代码通俗易懂，答案简单直观，非常棒

[CBGhaha]

generator +Interator接口实现深度遍历

function *DFS(tree){
    yield tree;
    let children=tree.children;
    if(children){
        for(let i in children){
            yield *DFS(children[i])
        }
    }
}
console.log([...DFS(tree)])