广度优先搜索

Posted on In

广度优先搜索

在 N * M 的网格中，从 start 走到 end 。
广度解法：需要一个队列，从 start 节点开始，当一个节点抛出时，将它周围的节点入队，直至抛出的节点是 end 节点。
模拟网格：

1
2
3
4
5
6
7
8
9
10
11
var map = [
  // map[x][y]
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 2],
]
find(map)

算法：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
function find(map) {
  var maxX = map.length - 1, // 最大 x 坐标
    maxY, // 最大 y 坐标
    queue = [], // 寻路队列
    start_x = -1, // 起始位置 x 坐标
    start_y = -1, // 起始位置 y 坐标
    end_x = -1, // 结束位置 x 坐标
    end_y = -1, // 结束位置 y 坐标
    unpassed = [] // 用于判断是否经过的数组

  // 如果数组长度为0，返回
  if (maxX >= 0) {
    maxY = map[0].length - 1
  } else {
    return
  }

  // 寻找起始坐标和终止坐标
  for (let i = 0, len = map.length; i < len; i++) {
    for (let j = 0, innerLen = map[i].length; j < innerLen; j++) {
      if (map[i][j] == 1) {
        start_x = i
        start_y = j
      }
      if (map[i][j] == 2) {
        end_x = i
        end_y = j
      }
    }
    if (start_x != -1 && end_x != -1) break
  }

  // 缺少起始位置或者结束位置
  if (start_x == -1 || end_x == -1) {
    console.log("地图有误")
    return
  }

  // 初始化路径数组
  for (let i = 0, len = map.length; i < len; i++) {
    var result = []
    for (let j = 0, innerLen = map[i].length; j < innerLen; j++) {
      result.push(true)
    }
    unpassed.push(result)
  }

  // 起始位置进入队列
  queue.push([start_x, start_y])

  do {
    // 取出当前位置
    var [current_x, current_y] = queue.shift()

    // 判断是否经过
    if (unpassed[current_x][current_y]) {
      unpassed[current_x][current_y] = false
    } else {
      continue
    }

    // 打印路径数组
    show(unpassed)

    // 到达终点
    if (current_x == end_x && current_y == end_y) break
    else {
      // 上方位置入队
      if (current_x > 0) {
        queue.push([current_x - 1, current_y])
      }

      // 右方位置入队
      if (current_y < maxY) {
        queue.push([current_x, current_y + 1])
      }

      // 下方位置入队
      if (current_x < maxX) {
        queue.push([current_x + 1, current_y])
      }

      // 左方位置入队
      if (current_y > 0) {
        queue.push([current_x, current_y - 1])
      }
    }
  } while (true)
}

function show(map) {
  for (let i = 0, len = map.length; i < len; i++) {
    var str = ""
    for (let j = 0, innerLen = map[i].length; j < innerLen; j++) {
      if (!map[i][j]) {
        str += "*"
      } else str += "0"
    }
    console.log(str)
  }
  console.log("------")
}