3
$\begingroup$

In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up considering $2|E| = O(|E|)$ vertices total because $\sum_{v \in V} d_v = 2|E|$. What I don't understand is why we even bother specifying $O(|V| + |E|)$ in the first place because it seems to me that the tightest bound you can really have in any situation is $O(|E|)$. I.e., it seems to me that the $O(|V|)$ doesn't help you at all. To see why, consider two cases:

  • The graph is connected. Then of course $|E| \ge |V - 1|$.
  • The graph isn't connected. Then you are "stuck" in the connected component you start in. Once again, inside the connected component $A$ you start in you have $|E_A| \ge |V_A - 1|$. Maybe there are more edges and vertices elsewhere. But once again the $O(|V|)$ seems redundant.

Another way I think about it: Adding a vertex alone doesn't create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $O(|V|)$ useful?

$\endgroup$
3
$\begingroup$

You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

S <- new empty set
T <- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v <- remove some element from T
        add v to S
        do something with v
        for each vertex w that is adjacent to v:
            if w is not in S and not in T:
                add w to T

Notice the outer loop on the variable u. This loop is present in some descriptions of DFS/BFS/etc. and absent in others. Why is this? The answer is that graph searches are used for different purposes. Sometimes, you have a particular start vertex u and you just want to search for everything that is reachable from u. However, other times you are using the graph search to find the connected components of the graph, or as part of an algorithm for computing some other property of the entire graph such as biconnected components. In these cases, the outer loop is necessary.

The crucial special property of graph search is that, even with the outer loop, the runtime is still bounded by $O(|V| + |E|)$, and not just by $O(|V| \cdot |E|)$. This property is what makes efficient algorithms possible for computing connected components, etc.


It's also worth noting that the $O(|V| + |E|)$ bound assumes that the white/gray/black status of a vertex (i.e. which set it is in) can be checked and modified in $O(1)$ time. This can be achieved by creating an array of size $V$, or by attaching a flag to each vertex; either way, it takes $O(V)$ time to initialize all the vertices into the white set at the start of the algorithm. If you don't use one of these methods, you probably have to add a logarithmic overhead for tracking the vertices in set data structures. This is true even in cases where you don't need the outer loop.

$\endgroup$
  • $\begingroup$ @kanso37 You have already accepted my answer, but make sure you also read my latest addendum at the bottom for another reason for the $|V|$ in the time bound. $\endgroup$ – Aaron Rotenberg Jan 29 at 6:27
1
$\begingroup$

I think you have answered your own question to some extent. Let $G$ be a graph with $V$ is the vertex set and $E$ is the edge set. Let $G$ is not connected, $|E| = \mathcal{O}(\log |V|)$. In this case runtime of BFS/DFS will be $\mathcal{O}(|V| + \log |V|)$ not $\mathcal{O}(\log |V|)$. If $|E| = \mathcal{O}(V)$ then there is no difference between $\mathcal{O}(|V|+ |E|)$ and $\mathcal{O}(|E|)$.

Here is case where writing $\mathcal{O}(|V|)$ is considered as a good than measuring complexity in terms of $\mathcal{O}(|V| + |E|)$. Let $G$ be a undirected graph and we want to find whether $G$ have a cycle or not. The complexity of this problem is $\mathcal{O}(|V|)$. This question can be found in the exercise section of Graph Search Algorithms of book Introduction to Algorithms by Coreman et.al.

Note: Adding a vertex cost you if you add vertices in large numbers. Let us consider the case where $|V| = |E|$ and you keep adding the veritces without adding edges such that new graph(with $V'$ vertex set and $E'$ edge set) have $|V'| = |E|^2$. Although you have not added any single edge still runtime increases by a large factor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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