为什么广度优先搜索（BFS）的时间复杂度为O(n+m)？

在最坏场景下，首个while循环需要遍历图中的全部节点，这部分开销为n量级。对于每个被访问的节点，算法都需要检查其所有邻接节点/边，我原本推导认为该过程的时间复杂度应该是 O(n * 最大节点度 deg(u))。

但检索到的所有解答都表示，由于算法仅需访问每个节点、每条边各一次，因此整体时间复杂度为 O(n + m)。这里的核心困惑是：遍历邻接节点/边的过程中会碰到已经访问过的重复节点，只是碰到这类已访问节点时不会将其重复加入待遍历列表，这类检查操作依然会产生运行时开销，为什么没有被计入总复杂度？

具体示例 #

对于结构为 a->b->c 的图，我们从节点a出发执行遍历：

• 从节点a出发，检查其邻接节点b，将b加入待遍历列表
• 接着前往节点b，从b出发检查邻接节点a和c，其中a是已访问节点，因此将c加入待遍历列表，之后再前往节点c
• 可见在从节点b向外探索的过程中，对应的操作数是O(2)，即O(deg(b))量级，并没有因为a是已访问节点就省去这次检查的时间开销。

内容的提问来源于stack exchange，提问作者13763824039