为何广度优先搜索（BFS）的时间复杂度是O(V+E)而非O(E)？

Great question—your observation about edges being traversed twice is spot-on, so let's unpack why we use O(V+E) instead of just O(E) for BFS's time complexity.

First, let's confirm your initial point: in an undirected connected graph, every edge is indeed processed twice (once from each endpoint's adjacency list), so the total number of inner loop iterations is 2*E. Since constant factors don't matter in big-O notation, this part of the algorithm is O(E) all by itself.

So why add the V term? Here's the breakdown:

1. BFS does more than just process edges
   Beyond traversing edges, BFS has several critical operations that scale with the number of nodes V:

   • Initializing a visited array (or hash set) to track which nodes have been processed—this takes O(V) time, since we have to mark every node as unvisited upfront.
   • Each node is enqueued exactly once and dequeued exactly once. These are O(1) operations per node, adding up to O(V) total time.
   • Marking a node as visited when we dequeue it—another O(V) operation, since we do this once per node.

2. Universal clarity for all graph types
   While your question focuses on connected graphs, the O(V+E) notation is designed to be universal. For example:

   • In a sparse connected graph (like a tree, where E = V-1), O(E) is equivalent to O(V), so O(V+E) simplifies to O(V)—which matches the actual runtime (since node operations and edge operations are both linear in V).
   • In a disconnected graph, you might have isolated nodes (with zero edges) or small connected components. Here, the V term becomes critical because the number of edges could be much smaller than the number of nodes, and O(V+E) accurately reflects that the algorithm still has to process all those nodes.

3. Big-O is about capturing all dominant costs
   Big-O notation describes the upper bound of an algorithm's runtime. Even though the edge processing is O(E), the node-related operations are O(V), so combining them gives us O(V+E). When E is much larger than V (like a dense complete graph where E ≈ V²), O(V+E) simplifies to O(E), which aligns with your observation. When E and V are roughly the same (like a tree), it simplifies to O(V). This notation neatly covers all scenarios without needing separate cases.

To put it in concrete terms:

• For a tree with 1000 nodes (999 edges), total operations are ~1000 (node tasks) + 1998 (edge tasks) = ~2998, which is O(V).
• For a complete graph with 1000 nodes (~500k edges), total operations are ~1000 + 1,000,000 = ~1,001,000, which is O(E).

O(V+E) captures both of these scenarios perfectly, which is why it's the standard way to express BFS's time complexity.

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