图的广度优先遍历的bug

Question

老师好，视频9-2里面说设置图节点visited放在子节点遍历以外会有问题，这里有点没理解，难道不是节点出队之后，这个节点就访问了，就应该添加到visited里面吗？
还麻烦老师举一个有问题的例子

Answer 1

lewis 2021-10-08 14:13:14

节点入队之后就应该标记为访问过，而不是在出队时候再标记

• 提问者 且听风吟720 #1

  标记的先后区别在哪儿呢……主要是这一点没有绕明白，没理解出队标记导致的问题

• lewis #2

  会导致重复遍历，比如节点a已经入队，但没有出队，就没有标记，进而，就会导致再次遇到节点a时候，误以为它没有遍历过，导致重复遍历

• 提问者 且听风吟720 #3

  举了个这种图的例子突然理解了……
  const graph = {
    0: [0, 1, 2, 3],
    1: [0, 1, 2, 3],
    2: [0, 1, 2, 3],
    3: [0, 1, 2, 3]
  }