2
$\begingroup$

In an undirected graph it takes $O(|V| + |E|)$ time to visit all nodes in a simple graph using BFS according to our lecture notes. But why can't you visit them all in $(|V|)$ time instead?

$\endgroup$

2 Answers 2

2
$\begingroup$

Particularly for BFS you need to pass over all edges. However, it is a lower bound for any algorithm for that — let's look at the simplified problem of testing whether the graph is connected. Let's look at the following two cases:

  1. The graph is made of two random connected graphs.
  2. The graph is made of two random connected graphs, with a single random edge connecting them.

To distinguish between those two cases, our algorithm MUST at some time process that edge which connects the two random graphs, which requires passing over all edges. Additionally, there is no possible way to eliminate any edge without examining it. We can see the algorithm must process all edges, so the complexity must be $\Omega(|E|)$.

$\endgroup$
2
  • $\begingroup$ Can this be turned into a proof? $\endgroup$
    – Simd
    Apr 25, 2023 at 16:09
  • $\begingroup$ A formal proof of this will depend on the exact way the graph is given and the computation model. But I believe that something like this argument would work for most reasonable input formats. $\endgroup$ Apr 26, 2023 at 3:26
0
$\begingroup$

You are correct in that for many representations of graphs, you could iterate through all the nodes in $O(|V|)$ time. But if someone wants to visit all the nodes according to a BFS order (for instance, producing the BFS tree on |V| nodes) it will require $O(|V|+|E|)$ time. That is, if one wants to process the nodes in some order where each newly-visited node is adjacent to a previously-visited node (if such nodes exist -- which they always do if the graph is connected) then this will require a BFS traversal of $O(|V|+|E|)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.