广度优先 和 深度优先

00.md

• BFS：广度优先搜索
• DFS：深度优先搜索

BFS 的重点在于队列，而 DFS 的重点在于递归。

namespace A {
  export interface Node {
    value: number,
    children: Array<Node>,
  };
}

const nodes: Array<A.Node> = [
  {
    value: 1,
    children: [
      {
        value: 2,
        children: [
          {
            value: 3,
            children: [],
          },
          {
            value: 4,
            children: [],
          },
        ],
      },
      {
        value: 5,
        children: [],
      },
      {
        value: 6,
        children: [
          {
            value: 7,
            children: [],
          },
        ],
      },
    ],
  },
  {
    value: 8,
    children: [
      {
        value: 9,
        children: [],
      },
      {
        value: 10,
        children: [],
      },
    ],
  },
];

function bfs(nodes: Array<A.Node>) {
  const queue = new Array(...nodes);
  const result = new Array();
  while(queue.length) {
    const node = queue.shift();
    result.push(node.value);
    queue.push(...node.children);
  }
  return result;
}

function dfs(nodes: Array<A.Node>) {
  const result = new Array();
  nodes.forEach(node => {
    result.push(node.value);
    result.push(...dfs(node.children));
  });
  return result;
}

console.log(`bfs:`, bfs(nodes));
console.log(`dfs:`, dfs(nodes));

运行结果：

bfs: [ 1, 8, 2, 5, 6, 9, 10, 3, 4, 7 ]
dfs: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

从遍历顺序中可以看出来差别。