DFS & BFS - JavaScript

通常遍历树结构：深度优先遍历（DFS）和广度优先遍历（BFS）。

树结构数据如下：

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
const tree = {
  value: '1',
  children: [
    {
      value: '2',
      children: [
        {
          value: '4',
          children: []
        },
        {
          value: '5',
          children: []
        }
      ]
    },
    {
      value: '3',
      children: [
        {
          value: '6',
          children: []
        },
        {
          value: '7',
          children: []
        }
      ]
    }
  ]
}

DFS

收集节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function dfs(root) {
  const collections = []

  const process = (arr) => {
    if (!arr || !arr.length) return
    for (let i = 0; i < arr.length; i++) {
      const node = arr[i]
      collections.push(node.value)
      process(node.children)
    }
  }
  process([root])
  return collections
}

搜寻目标节点

找到目标节点值，并返回多少步，未找到目标值，返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function dfsSearch(root, target) {
  let steps = 0

  const process = (nodes, target) => {
    for (const node of nodes) {
      if (node.value === target) {
        return steps + 1
      }
      steps++
      if (node.children.length) {
        const result = process(node.children, target)
        if (result !== -1) return result
      }
    }
    return -1
  }

  return process([root], target)
}

BFS

收集节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
function bfs(root) {
  const collections = []
  const queue = [root]

  while (queue.length) {
    const node = queue.shift()
    collections.push(node.value)
    for (const item of node.children) {
      queue.push(item)
    }
  }
  return collections
}

搜寻目标节点

找到目标节点值，并返回多少步，未找到目标值，返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bfsSearch(root, target) {
  let steps = 0
  const queue = [root]

  while (queue.length) {
    const temp = queue.shift()
    if (temp.value === target) {
      return steps + 1
    }
    steps++
    if (temp.children.length) {
      temp.children.forEach(element => {
        queue.push(element)
      });
    }
  }

  return -1
}