广度优先搜索解决欧拉回路时间复杂度_广度优先搜索

Don老师，师出北师大实验，深造于北大。在加州大学完成了博士学位，先后工作于微软研究院和谷歌，斩落无数offer，日常生活在LC长期霸榜。

今天Don老师为我们带来，算法面试的常见题目类型 ---- 广度优先搜索。

*内容部分取材于互联网，侵删

01  

迷宫最短路径

Shortest path in maze

广度优先搜索常用于解决：各种最短路问题

经典问题：迷宫最短路问题

广度优先搜索的序：距离搜索起点的距离

实现方法：主要通过队列实现

算法如下：

(1) 起点放入队列

(2)每次展开队列头，不重复展开

(3)重复(2)直至队列空

02 

实现方法

Implementation

问题1：这里的visit数组实在每次pop之后改，对么？visit数组能不能在每次push之后改？

问题2：这里的visit数组实在每次pop之后改，对么？visit数组能不能在每次push之后改？

03 

图论中的BFS

BFSG in raph

灵魂拷问：

(1)图上的BFS和树上的BFS有哪些区别？

(2)树上的BFS和图上的BFS复杂度是多少？

(3)迷宫问题是树上的BFS还是图上的BFS？

下期将会由Don老师继续为大家带来，深度优先搜索的相关小结，敬请期待。