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

广度优先搜索(BFS)和深度优先搜索(DFS)是计算机科学和数据分析中使用的两种基本算法,用于遍历和搜索图、树等数据结构。

这些算法可以应用于许多问题,例如找到两点之间的最短路径,检查图中的循环,或搜索数据结构中的特定元素。

        1
      /   \
     2     3
    / \   / \
   4   5 6   7
1
2
3
4
5

以上结构,javascript 代码表达如下:

let tree = [
  {
    id: '1',
    name: '1',
    children: [
      {
        id: '2',
        name: '2',
        children: [
          {
            id: '4',
            name: '4',
            children: []
          },
          {
            id: '5',
            name: '5',
            children: []
          }
        ]
      },
      {
        id: '3',
        name: '3',
        children: [
          {
            id: '6',
            name: '6',
            children: []
          },
          {
            id: '7',
            name: '7',
            children: []
          }
        ]
      }
    ]
  },
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

深度优先遍历(Depth-First Search, DFS)

递归实现

function dfs(tree, func) {
  tree.forEach((node) => {
    func(node)
    node.children && dfs(node.children, func)
  })
}
1
2
3
4
5
6

循环实现

function dfs(tree, func) {
  let node, curTree = [...tree]
  while ((node = curTree.shift())) {
    func(node)
    node.children && curTree.unshift(...node.children)
  }
}
1
2
3
4
5
6
7

输出结果:

dfs(tree, (node) => {
  console.log(node.name);
})
// 1, 2, 4, 5, 3, 6, 7
1
2
3
4

广度优先遍历(Breadth-First Search, BFS)

function bfs(tree, func) {
  let node, curTree = [...tree]
  while ((node = curTree.shift())) {
    func(node)
    node.children && curTree.push(...node.children)
  }
}
1
2
3
4
5
6
7

输出结果:

bfs(tree, (node) => {
  console.log(node.name);
})
// 1, 2, 3, 4, 5, 6, 7
1
2
3
4

Ref

Last Updated: 9/26/2024, 6:11:55 AM