有向图中能否实现时间复杂度O(m)的BFS？无向图BFS时间为O(m+n)

首先，BFS的时间复杂度核心由被访问的顶点数k和被访问的边数l决定，即O(k + l)。下面分情况讨论：

可以实现O(m)复杂度的场景 #

• 仅遍历可达子图：如果从起点出发的BFS只遍历可达的顶点和边，那么被访问的顶点数k ≤ l + 1（最坏是链式结构，顶点数比边数多1）。当遍历所有边（l=m）时，k=O(m)，此时O(k + l)等价于O(m)。
• 图中无大量孤立顶点：若整个图的顶点数n满足n=O(m)（比如每个顶点至少关联一条边），即使遍历所有顶点和边，O(n + m)的渐近复杂度也等于O(m)。

无法实现O(m)复杂度的场景 #

如果图中存在远多于边数的孤立顶点（比如n=1000m），且BFS需要对所有顶点执行初始化操作（比如标记访问状态），这一步的时间成本是O(n)，远大于O(m)，导致总复杂度无法降到O(m)。

总结：只要不需要处理数量远超边数的孤立顶点，有向图的BFS就能达到O(m)的时间复杂度。

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