深度优先搜索与广度优先搜索

Question

所以，经过多年的自学，我想我已经准备好站在巨人的肩膀上，问你一个好问题了！

我有一棵节点树。我想要的是一个函数，返回按深度排序的整个树的数组。

在我最初的尝试中，我当时并没有意识到我正在执行深度优先搜索。

我的解决办法是：

• 递归地遍历这棵树，在我走的时候注释深度。
• 根据深度注释对上面的内容进行排序。
• 筛选出深度注释并返回排序数组。

那是调用3个循环的三个步骤！于是有人提醒我注意广度优先搜索的概念。我做了我的研究，并建立了(我自己)的BFS功能！它看上去很简单，做了我需要的事。

然后，当我对这两个版本进行计时时；完全令人费解；笨重的DFS版本更快！为什么？

这里是我的深度优先搜索：

function dfsElementsInTree(input){
  // perform depth first search but
  // return a depth sorted array of an element or elements and any children
  let output = [];

  if (Symbol.iterator in input)
    // input is a HTMLcollection
    for (const element of input)
      doTraversal(element);
  else
    doTraversal(input);
  
  return output.sort((a, b) => a.depth - b.depth).map(item=>item.element);

  function doTraversal(element, depth=0) {
    output.push({element, depth});
    if (element.children.length) depth++;
    for (const child of element.children)
      doTraversal(child, depth);
  }
}

这里是我的广度优先搜索：

function bfsElementsInTree(input) {
  // perform a breadth first search in order to have elements ordered by depth.
  let output = [];
  let queue = [];
  let visited = [];
  const enqueue = item => {queue.push(item); visited.push(item);};

  if (Symbol.iterator in input)
    // input is a HTMLcollection
    for (const element of input)
      queue.push(element);
  else
    queue.push(input);
  
  while (queue.length) {
    for (const element of queue)
      for (const child of element.children)
        if (!visited.includes(child))
          enqueue(child);
    output.push(queue.shift());
  }
  
  return output;
}

准备在这里进行基准测试：https://jsben.ch/ZNuAx

但是，如果您想自己测试它，下面是一些生成树的代码：

// Create trees of divs as such:
// (left to right)
// 1
// 1 -> 2
// 1 -> 2 -> 3
// 1 -> 2
// 1

const a1 = document.createElement('div');
const a2 = document.createElement('div');
const a3 = document.createElement('div');
const a4 = document.createElement('div');
const a5 = document.createElement('div');

[a1,a2,a3,a4,a5].forEach(e => e.className ='1');

const b2 = document.createElement('div');
const b3 = document.createElement('div');
const b4 = document.createElement('div');

[b2,b3,b4].forEach(e => e.className ='2');

const c3 = document.createElement('div');

c3.className = '3';

a2.appendChild(b2);

b3.appendChild(c3);
a3.appendChild(b3);

a4.appendChild(b4);

[a1,a2,a3,a4,a5].forEach(e => document.body.appendChild(e));

非常感谢你抽出时间。有个专家看着我的肩膀真是太好了！

Answer 1

我解决了。原来我的循环逻辑有点出格了。不需要一段时间和一段时间！)当我们在做的时候，我们不需要检查是否拜访过。谢谢@vnp在评论中)

编辑:因为我实际上没有使用队列，所以我忽略了现在不需要维护两个数组！谢谢@Ry在评论中！)

为了速度又写了一遍，下面是：

  function bfsElementsInTree(input) {
    // perform a breadth first search in order to have elements ordered by depth. (Deepest last)
    let output = [];

    if (Symbol.iterator in input)
      // input is a HTMLcollection
      for (let i = 0, max = input.length; i < max; i++)
        output[i] = input[i];
    else
      output.push(input);

    for (let i = 0; i < output.length; i++) {
      const children = output[i].children;
      for (let j = 0, max = children.length; j < max; j++)
        output.push(children[j]);
    }

    return output;
  }

和新的基准：https://jsben.ch/F1zzW