BFS入门
BFS 问题的本质通常是让你在一副“图”中找到从起点 start 到终点 target 的最短距离。BFS的思想不多说,直接上模板。
1 | int BFS(Node start, Node target){ |
注:
1.cur.adj()
泛指节点的相邻节点
2.visited
的作用是不走回头路,只访问没有访问过的节点,一般情况下都是必要的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路,就不需要visited
3.这里需要入队时就记录visited
,如果出队时再记录就有可能重复入队,比如有两个节点同时可以到达下一个节点,那么该节点就会重复入队。还有一个解决方案可以在出队时记录,就是出队时再查看该节点是否被访问过,访问过就continue
,但是这种方法并不可取,这样会导致队列中的冗余,造成更大的空间复杂度。虽说visited
的作用时访问没有访问过的节点,但是入队时记录,同样是使所有节点依次访问,即只要进队列了就算访问了,因为迟早是要访问的。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ae86's Blog!