概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？
2.14补充
对象的深拷贝

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

问下大佬，有个旧的json 格式转成新的json格式

var old ={
"颜色":[
{
"黄色":{
"尺码":[
{
"XL":{
"形状":[
{
"多边形":1
},
{
"方形":2
}
]
}
},
{
"M":{
"形状":[
{
"方形":3
}
]
}
}
]
}
},
{
"红色":{
"尺码":[
{
"XL":{
"形状":[
{
"多边形":1
},
{
"方形":2
}
]
}
},
{
"M":{
"形状":[
{
"方形":3
}
]
}
}
]
}
}
]
}

var new =[
{
// priceId: 1,
// price: 35.0,
// "stock": 8,
"attrValueList": [
{
"attrKey": "颜色",
"attrValue": "黄色",
"attrCode": "1001"
},
{
"attrKey": "尺码",
"attrValue": "xm",
"attrCode": "2001"
},
{
"attrKey": "形状",
"attrValue": "多边形",
"attrCode": "3001"
}

    ]
  },
  {
    // priceId: 1,
    // price: 35.0,
    // "stock": 8,
    "attrValueList": [
      {
        "attrKey": "颜色",
        "attrValue": "黄色",
        "attrCode": "1001"
      },
      {
        "attrKey": "尺码",
        "attrValue": "L",
        "attrCode": "2001"
      },
      {
        "attrKey": "形状",
        "attrValue": "多边形",
        "attrCode": "3001"
      }

    ]
  },
  {
    // priceId: 1,
    // price: 35.0,
    // "stock": 8,
    "attrValueList": [
      {
        "attrKey": "颜色",
        "attrValue": "黄色",
        "attrCode": "1001"
      },
      {
        "attrKey": "尺码",
        "attrValue": "L",
        "attrCode": "2001"
      },
      {
        "attrKey": "形状",
        "attrValue": "五边形",
        "attrCode": "3001"
      }

    ]
  }

]
有方便的转换方法吗

from daily-interview-question.

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

2.14补充
对象的深拷贝

from daily-interview-question.

图

图是一种复杂的非线性结构，它由边（边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

测试成功

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

from daily-interview-question.

深度优先：找到一个节点后，把它的后辈都找出来，最常用递归法。
广度优先：找到一个节点后，把他同级的兄弟节点都找出来放在前边，把孩子放到后边，最常用 while

from daily-interview-question.

深度优先遍历

遍历结果是： 1->2->4->8->5->3->6->7
广度优先遍历

遍历结果是：1->2->3->4->5->6->7->8

from daily-interview-question.

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)])

from daily-interview-question.

我举个通俗的例子
假如你的面前摆了一排杯子，每个杯子里都装了不确定量的水。

深度优先遍历就是你拿起第一个杯子，喝光水，然后再拿起下一个杯子，喝光，一直到最后一个杯子。

广度优先遍历就是你从第一个杯子开始，每个杯子挨个都喝一口，然后又重头开始挨个喝一口，一直到全部喝完为止。

是这样吧？

from daily-interview-question.

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

from daily-interview-question.

第五题问的是深度优先遍历和广度优先遍历，我是从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

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

感谢楼主的回答，了解到了深度遍历和广度遍历区别，小白把代码放在codepen实现了一遍。https://codepen.io/valleylmh/pen/EBBrWg

from daily-interview-question.

二叉树

var myTree = {
    val: 6,
    left: {
      val: 5, 
      left: { 
        val: 4 
      }, 
      right: { 
        val: 3 
      }
    },
    right: { 
      val: 2, 
      right: { 
        val: 1 
      } 
    }
}

广度优先遍历 BFS

思路是利用队列，从根节点开始，依次将左节点、右节点push进数组。

function bfs (tree) {
    var queue = [tree]
    var res = []
    var count = 0
    while (queue[count] && queue[count].val) {
        res.push(queue[count].val)
        var left = queue[count].left
        var right = queue[count].right
        if (left) {
            queue.push(left)
        }
        if (right) {
            queue.push(right)
        }
        count++
    }
    return res
}

深度优先遍历 DFS

思路是利用栈，从根节点开始，依次将右、左节点入栈。

// 非递归版本
function dfs (tree) {
    var stack = [tree]
    var res = []
    while (stack.length) {
        var node = stack.pop()
        res.push(node.val)
        var left = node.left
        var right = node.right
        if (right) stack.push(right)
        if (left) stack.push(left)
    }
    return res
}

from daily-interview-question.

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

这个是深度优先的，你看看它最后的循环，是从末尾开始，也就是说，再下一次循环进来的时候，每次出栈都是从后面最后一个开始[其实已经到了子节点的范畴了】，[(当前节点的子节点是被放在栈的后面）

from daily-interview-question.

宽度优先遍历 和 深度优先遍历 是 遍历 或者 搜索 图 和 树 的算法。

深度优先遍历： 从根节点开始，沿着树的深度遍历树的节点，尽可能深的搜索树的分支。沿着一条可能的路径一直往下走，深入到不能深入为止。【可以纵向优先搜索】

宽度优先遍历： 从根节点开始，沿着树的宽度遍历树的节点。横向一层(level)的去遍历。

一楼大兄弟的html代码：

  <div class="parent">
      <div class="child-1">
          <div class="child-1-1">
              <div class="child-1-1-1">
                a
              </div>
              <div class="child-1-1-2">
                b
              </div>              
          </div>
          <div class="child-1-2">
              <div class="child-1-2-1">
                c
              </div>    
          </div>     
          <div class="child-1-3">
                d
          </div>                 
      </div>
      <div class="child-2">
        <div class="child-2-1">
          e
        </div>
        <div class="child-2-2">
          f
        </div>        
      </div>
      <div class="child-3">
        <div class="child-3-1">
          g
        </div>
      </div>
  </div>

深度优先遍历 - 递归

    var dfs_recursive = function(root, res = []){
      res.push(root)
      for (let item of root.children) {
        dfs_recursive(item, res)
      }
      return res
    }
    console.log('1------------->>', dfs_recursive(root))

深度优先遍历 - stack 先进后出 【push(item) -> pop】 或者 [unshift(item) -> shift()]

    var dfs_stack = function(root) {
      const res = []
      const stack = []
      stack.push(root)
      while (stack.length != 0) {
        let item = stack.pop()
        res.push(item)
        for (let i = item.children.length - 1; i >= 0; i--) {
          stack.push(item.children[i])
        }
      }
      return res
    }
    console.log('2------------->>', dfs_stack(root))

广度优先遍历 - queue 先进先出[push(item) -> shift()] 或者[unshift(item) -> pop()]

    var bfs_queue = function(root) {
      const res = []
      const queue = []
      queue.push(root)
      while (queue.length != 0) {
        let currentLevelLength = queue.length
        for (let i = 0 ; i < currentLevelLength; i++) {
          let item = queue.shift()
          res.push(item)
          for (let j = 0; j < item.children.length; j++) {
            queue.push(item.children[j])
          }
        }
      }
      return res
    }
    console.log('3------------->>', bfs_queue(root))

from daily-interview-question.

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

from daily-interview-question.

这个字打错了吧

from daily-interview-question.

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？
2.14补充
对象的深拷贝

深拷贝感觉是用到了深度优先, 广度优先,我还没写过...我得研究下

从掘金的广度深拷贝问题过来的，结果全是在聊遍历，自己试着实现了一下广度拷贝，不知道有没有更好的方式。

const isArray = (a)=>{Array.isArray(a)};
const isObject = (o)=>Object.prototype.toString.call(o) === '[object Object]';

/**
* 广度优先深拷贝，借助队列实现，每个子节点入队列时，记录下它的新父节点以及他的key
*/

const bfsCopy = (src)=>{
  const queue = [];
  // 入队列操作
  const inQueue = (o,parent) => {
    for(let key in o){
        queue.push({
          parent, // 新的父节点
          key,  // 子节点的key
          node: o[key] // 子节点
        })
    }
  }
  if(isArray(src) || isObject(src)){
    const root = isArray(src) ? [] : {};
    // 将根节点的子节点入队列
    inQueue(src,root);
    // 开始遍历队列
    while(queue.length !== 0){
      // 取出队头元素 
      const { parent, key , node } = queue.shift();
      if(isArray(node) || isObject(node)){
          const r  = isArray(node) ? [] : {};
          parent[key] = r;
          inQueue(node,r)
      }else{
          parent[key] = node;
      }
    }
    return root;
  }
  return src;
}

from daily-interview-question.

附上结果图：

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(
  1,
  new TreeNode(2, null, new TreeNode(4)),
  new TreeNode(3, new TreeNode(5))
);
console.log(root);

function dfs(root) {
  if (!root) return;
  console.log(root.val);
  dfs(root.left);
  dfs(root.right);
}
function bfs(root) {
  if (!root) return
  const queue = []
  queue.push(root)
  while(queue.length){
    let len = queue.length
    for(let i = 0; i < len; i++){
      let cur = queue.shift()
      console.log(cur.val);
      if(cur.left) queue.push(cur.left)
      if(cur.right) queue.push(cur.right)
    }
  }
}

console.log("------------------dfs-----------------");
dfs(root);
console.log("------------------bfs-----------------");
bfs(root);

from daily-interview-question.

给sisterAn的回复加上了一些配图,方便理解

图

图是一种复杂的非线性结构,他由边(Edge)和点(Vertex)组成.
一条边链接的两个点称为相邻顶点.

G = (V, E)

图分为:

• 有向图
• 无向图

本文探讨的是无向图

图的表示

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

• 邻接矩阵:使用二维数组来表示点与点之间是否有边,如 arr[i][j] = 1表示节点 i 与节点 j 之间有边,arr[i][j] = 0表示节点 i 与节点 j 之间没有边. (有向图使用邻接矩阵空间复杂度较大,0是没有用的信息)

• 邻接表：邻接表是图的一种链式储存结构，这种结构类似树的子链表，对于图中的每一个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就是顶点Vi的邻接表，单链表一般由数组或字典结构表示。

创建图

Vertex用数组结构表示,Edge用[[Set、Map、WeakSet 和 WeakMap 的区别#字典 Map|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) {
  if (v === w) return;
  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 () {
  let s = "";
  for (const vertex of this.vertices) {
    s += vertex + " -> ";
    const neighbors = this.edges.get(vertex);
    for (const neighbor of neighbors) {
      s += neighbor + " ";
    }
    s += "\n";
  }
  return s;
};

测试:

// 测试
const graph = new Graph();
const vertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (v of vertices) {
  graph.addVertex(v);
}

graph.addEdge("A", "B");
graph.addEdge("A", "F");

graph.addEdge("B", "C");
graph.addEdge("B", "I");
graph.addEdge("B", "G");

graph.addEdge("C", "D");
graph.addEdge("C", "I");

graph.addEdge("D", "E");
graph.addEdge("D", "H");
graph.addEdge("D", "G");
graph.addEdge("D", "I");

graph.addEdge("E", "F");
graph.addEdge("E", "H");

graph.addEdge("F", "G");

graph.addEdge("H", "G");

console.log(graph.toString());
// A -> B F       
// B -> A C I G   
// C -> B D I     
// D -> C E H G I 
// E -> D F H     
// F -> A E G     
// G -> B D F H   
// H -> D E G     
// I -> B C D    

测试成功

图的遍历

两种遍历算法：

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

深度优先遍历(DFS)

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

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

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

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

步骤

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

实现

Graph.prototype.dfs = function () {
  // 原例子用的是数组 因为它存的顶点是number类型
  // 但我这边是string 所以使用map 同时也兼容number类型的情况
  const marked = new Map();
  const edges = this.edges;
  for (const vertex of this.vertices) {
    if (!marked.get(vertex)) {
      dfsVisit(vertex);
    }
  }

  function dfsVisit(u) {
    marked.set(u, true);
    console.log(u);
    const neighbors = edges.get(u);
    for (const w of neighbors) {
      if (!marked.get(w)) {
        dfsVisit(w);
      }
    }
  }
};

测试

graph.dfs();
// A
// B
// C
// D
// E
// F
// G
// H
// I

广度优先遍历(BFS)

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

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

步骤

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

这边我有个疑问 我们做的是遍历 好像并不是搜索

实现

Graph.prototype.bfs = function (v) {
  const queue = [];
  const marked = new Map();
  marked.set(v, true);
  queue.push(v); //添加到队尾
  while (queue.length > 0) {
    const s = queue.shift(); //从队首移除
    if (this.edges.has(s)) {
      console.log(s);
    }
    const neighbors = this.edges.get(s);
    for (const w of neighbors) {
      if (!marked.get(w)) {
        marked.set(w, true);
        queue.push(w);
      }
    }
  }
};

测试

graph.bfs("A");
// A
// B
// F
// C
// I
// G
// E
// D
// H

from daily-interview-question.

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

2.14补充
对象的深拷贝

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

from daily-interview-question.

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

2.14补充
对象的深拷贝

Dom树的遍历

from daily-interview-question.

@caihg 我也是这样想的

from daily-interview-question.

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

2.14补充
对象的深拷贝

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

from daily-interview-question.

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

from daily-interview-question.

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

2.14补充
对象的深拷贝

数组扁平化

from daily-interview-question.

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

为啥是广度的啊？deepTraversal3 不是把当前节点的所有子节点遍历出来之后，在遍历下一个同胞节点吗？

from daily-interview-question.

深度优先搜索以及广度优先搜索实现方式

from daily-interview-question.

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

2.14补充
对象的深拷贝

深拷贝感觉是用到了深度优先, 广度优先,我还没写过...我得研究下

from daily-interview-question.

感觉广度优先遍历使用的stack 应该使用queue 更合适吧 就是先push进去的 先shift(）取出来 放在nodes里

from daily-interview-question.

第五题问的是深度优先遍历和广度优先遍历，我是从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

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

所有的方法都缺少对 node.chilren的非空判断，如果对象没有children属性则会报错

from daily-interview-question.

深度遍历

var deep=(node,fn)=>{
  fn(node);
  if(node.children){
    for(let i=0;i<node.children.length;i++){
      deep(node.children[i],fn);
    }
  }
};

广度遍历

var wide=(node,fn)=>{
  var queue = [];
  queue.push(node);
  while (queue.length != 0) {
    let item = queue.shift();
    fn(item);
    for (let j = 0; j < item.children.length; j++) {
      queue.push(item.children[j])
    }
  }
};

测试代码

var parent=document.getElementsByClassName('parent')[0];
wide(parent,(node)=>{
  console.log(node.className);
});
deep(parent,(node)=>{
  console.log(node.className);
});

from daily-interview-question.

我看大家广度优先都用两个数组做，其实用一个就可以了 ，利用for循环每次计算length的特性
广度优先遍历
`

function widthTraversal(node,nodeList = []){
    if(!node){
        return []
    }
    nodeList.push(node)
    for(let a = 0; a<nodeList.length;a++){
        let thisNode = nodeList[a]
        for(let i = 0; i< thisNode.children.length; i++){
            nodeList.push(thisNode.children[i])
        }
    }
    return nodeList
}

`

from daily-interview-question.

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

2.14补充
对象的深拷贝

遍历树型结构对象啊

from daily-interview-question.

const data = [{
       name: 'a',
       children: [{
           name: 'a1',
           children: [{
               name: 'a11'
           }, {
               name: 'a12'
           }]
       }, {
           name: 'a2',
           children: [{
               name: 'a21'
           }, {
               name: 'a22'
           }]
       }, {
           name: 'a3',
           children: [{
               name: 'a31'
           }, {
               name: 'a32'
           }]
       }, ],
   }, {
       name: 'b',
       children: [{
           name: 'b1',
           children: [{
               name: 'b11'
           }, {
               name: 'b12'
           }]
       }, {
           name: 'b2',
           children: [{
               name: 'b21'
           }, {
               name: 'b22'
           }]
       }, {
           name: 'b3',
           children: [{
               name: 'b31'
           }, {
               name: 'b32'
           }]
       }, ],
   }];

   let result = [];
   // 深度遍历

   function deep(ary) {
       for (const val of ary) {
           result.push(val.name);
           if (Array.isArray(val.children)) {
               deep(val.children);
           }
       }
       return result.join(',');
   }
   // const str = deep(data);

   // 广度遍历

   function bfs(ary) {   // 对比了下楼上的,我发现我这运行效率有点低,233333
       let quee = [];
       for (let i = 0; i < ary.length; i++) {
           result.push(ary[i].name);
           if (Array.isArray(ary[i].children)) {
               quee.push(...ary[i].children);
               if (i === ary.length - 1) {
                   bfs(quee);
               }
           }
       }
       return result.join(',');
   }

   const str = bfs(data);
   console.log(str);

from daily-interview-question.

第五题问的是深度优先遍历和广度优先遍历，我是从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

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

第二个广度和第一个不是一样的嘛

from daily-interview-question.

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

为啥是广度的啊？deepTraversal3 不是把当前节点的所有子节点遍历出来之后，在遍历下一个同胞节点吗？

没毛病的，循环是倒序。就是深度

from daily-interview-question.

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

获取项不一样 一个用到了pop 一个用shift

from daily-interview-question.

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

2.14补充
对象的深拷贝

DFS 可以用在查找两个 dom 节点的相同祖先节点

from daily-interview-question.

数组扁平化

const DFS = (arr, cb) => {
  const queue = []
  let idx = 0, length = arr.length - 1
  while(idx <= length) {
    if (Array.isArray(arr[idx])) {
      DFS(arr[idx], cb)
    } else {
      queue.push(arr[idx])
      cb(queue.shift())
    }
    idx++
  }
}

const BFS = (arr, cb) => {
  const queue = [arr]
  while(queue.length > 0) {
    let item = queue.shift()
    if (Array.isArray(item)) {
      for (let i = 0; i < item.length; i++) {
        queue.push(item[i])
      }
    } else {
      cb(item)
    }
  }
}

DFS([1, [2, 3, [4, 88]], [9, 45], 5, 6], (value) => {
  console.log('DFS value :>> ', value);
})

BFS([1, [2, 3, [4, 88]], [9, 45], 5, 6], (value) => {
  console.log('BFS value :>> ', value);
})

from daily-interview-question.

var arr = [
    {
        label: '1',
        children: [
            {
                label: '1-1',
                children: null
            },
            {
                label: '1-2',
                children: [
                    { label: '1-2-1', children: null},
                    { label: '1-2-2', children: null},
                ]
            }
        ]
    },
    {
        label: '2',
        children: [
            {
                label: '2-1',
                children: [
                    { label: '2-2-1', children: null },
                    { label: '2-2-2', children: null },
                ]
            },
            {
                label: '2-2',
                children: [
                    { label: '2-2-1', children: null},
                ]
            }
        ]
    }
]

// 深度优先：
let nodeList = [];
function deepTraversal(arr) {
    for (const n of arr) {
        nodeList.push(n.label);
        if (n.children) deepTraversal(n.children);
    }
}
deepTraversal(arr)
console.log('nodeList', nodeList)

// 广度优先：
var nodeList2 = [];
function widthTraversal(arr) {
    let stack = [];
    for (const n of arr) {
        nodeList2.push(n.label);
        if (n.children) stack = [...stack, ...n.children]
    }
    if (stack.length) widthTraversal(stack);
}
widthTraversal(arr);
console.log('nodeList2', nodeList2)

from daily-interview-question.

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

2.14补充 对象的深拷贝

我在业务中有用到过：
1、富文本“一键排版”
2、树形组件，拖动排序，数据递归处理等

from daily-interview-question.

概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？
2.14补充
对象的深拷贝

Dom树的遍历

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

这个打印出来是深度优先哟，实践一下再说，别误导了

from daily-interview-question.

from daily-interview-question.

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

在做后台管理系统的时候，遇到了这样的需求：左侧做成无限级目录，右侧上方面包屑要显示对应的路径。

这个时候有两种方案：
1.让后端提供一个接口，直接将路径array返回给前端
2.让后端在每一个目录node中加上其对应的father node的id。前端自己进行处理，处理方法如下：

• a. 写一个递归函数，将整个树摊平，输出一个一维数组
• b. 递归此一维数组，通过fid不断寻找其父节点，最终输出一个nodes路径

from daily-interview-question.

from daily-interview-question.

菜狗子前端分享一下自己的总结，如有不足欢迎指出！

dfs和bfs

导览：
dfs：递归和栈
bfs：队列

图

图的构造函数和方法

//撰写图的构造函数和方法
function Graph() {
  this.vertices = [];
  this.edges = new Map();
}

Graph.prototype.addVertex = function (v) {
  this.vertices.push(v);
  this.edges.set(v, []); //给顶点set一个边集合（空）
};

Graph.prototype.addEdge = function (v, w) {
  if (v === w) return;
  //分别拿到v w 的相邻点集合 push进去 不需要再set
  this.edges.get(v).push(w);
  this.edges.get(w).push(v);
};

图的dfs

• 循环traversal所有顶点
• traversal中：在循环中递归traversal
• 会越来越深 由于记录了已遍历的点所以不会重复遍历

//Depth First Search
Graph.prototype.dfs = function () {
  //图的dfs需要一个map来存放traversal过的顶点
  //因为不是树形结构 所以会出现traversal回来的情况
  const marked = new Map();
  //储存变量方便traversal函数使用 因为this是undefined
  const edges = this.edges;
  //遍历所有的点
  for (const vertex of this.vertices) {
    //若没有被traversal过 则traversal它
    if (!marked.get(vertex)) {
      traversal(vertex);
    }
  }
	//函数声明会提升 但是const定义变量不会提升 
	//所以edges要在前面定义好了
  function traversal(u) {
    marked.set(u, true);
    //操作
    console.log(u, "-dfsTraversal");
    const neighbors = edges.get(u);
    //** 一直往下遍历
    for (const w of neighbors) {
      if (!marked.get(w)) {
        traversal(w);
      }
    }
  }
};

此外还可以使用入栈出栈的方法，见下文

图的bfs

• 需要一个起始点（其实不要也可以，从任意顶点开始即可）
• 需要维护一个队列，入队的点视为已被遍历 `marked.set(v,true)
• 通过while循环，当队列为空时则结束遍历
• 将队列（shift）改为栈(pop)，就会变为dfs

//Breadth First Search
//需要一个起始节点
Graph.prototype.bfs = function (v) {
  if (!this.edges.has(v)) {
    console.log("需要一个正确的起始节点");
    return;
  }
  //需要维护一个队列
  const queue = [];
  const marked = new Map();
	//添加到队尾
  queue.push(v);
  //入队marked设置为true
  marked.set(v, true);
  while (queue.length > 0) {
    //remove first element 出队
    const u = queue.shift();
    //操作
    console.log(u, "-bfsTraversal");
    //需要将它的neighbor中未被遍历过的点加入队列
    const neighbor = this.edges.get(u);
    for (const w of neighbor) {
      //保证队列里都是未被遍历过的顶点
      if (!marked.get(w)) {
        //**只要进入了队列 就当做被遍历过 marked中设置为true
        //这样可以避免无限向队列里添加点
        marked.set(w, true);
        queue.push(w);
      }
    }
  }
};

树

和图的遍历最主要的区别是：不需要标记已遍历的节点。并且可以直接从顶端开始遍历（parent）

DOM树长这个样子：

<div class="parent">
	<div class="child-1">
		<div class="child-1-1">
			<div class="child-1-1-1"></div>
			<div class="child-1-1-2"></div>
		</div>
		<div class="child-1-2">
			<div class="child-1-2-1"></div>
		</div>
		<div class="child-1-3"></div>
	</div>
	<div class="child-2">
		<div class="child-2-1"></div>
		<div class="child-2-2"></div>
	</div>
	<div class="child-3">
		<div class="child-3-1"></div>
	</div>
</div>
<script>
	const node = document.querySelector(".parent");
	...
</script>

要求：按顺序打印出遍历的元素。

DOM节点的dfs

递归

• 很简单的递归遍历就是dfs

// 树的dfs不需要存marked标记 自上而下的递归就行了（因为不可能往回走）
const dfs1 = node => {
	if (node != null) {
		for (const child of node.children) {
			//操作
			console.dir(child);
			//递归
			dfs1(child);
		}
	}
	};

栈

• 如果想要和上面的方法输出一致，在入栈时需要倒着循环（因为是后进先出）

//不使用递归
const dfs2 = node => {
	const stack = [];
	if (node !== null) {
		stack.push(node);
		//while(stack.length)也行
		while (stack.length > 0) {
			//后进(push)先出(pop)
			const item = stack.pop();
			//操作
			console.dir(item, "stack");
			const children = item.children;
			//循环入栈children
			//倒着循环是为了和上述结果保持一致 for of 也可以
			for (let i = children.length - 1; i >= 0; i--) {
				stack.push(children[i]);
			}
		}
	}
};

DOM节点的bfs

队列

• 因为有父节点（parent）所以不需要像图那样需要传入一个起始点

const bfs = node => {
	const queue = [];
	if (node != null) {
		queue.push(node);
		while (queue.length > 0) {
			//出队
			const item = queue.shift();
			//操作
			console.dir(item);
			const children = item.children;
			//子节点入队
			for (const child of children) {
				queue.push(child);
			}
		}
	}
};

栈与队列在dfs和bfs时的区别

使用栈和队列时需要一个起始点，进行分解（对于图来说就是分解为相邻的点）

• 使用入栈出栈进行遍历是一个逐级连续分解的的过程:
  • 每次出栈相当于把节点分解为一群子节点又入栈
  • 下一次又将那群子节点的最后一个节点进行分解入栈
  • 如此循环下来，其实一直在往深了走
• 使用队列进行遍历是一个同级连续分解的过程：
  • 每次出队会将节点分解为一群子节点入队
  • 下一次会分解兄弟节点入队（如果有的话）
  • 如此循环下来，其实是一层一层的在分解

from daily-interview-question.