2
$\begingroup$

I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency matrix power is not optimal).

Complexity of BFS is O(V+E), running it for every vertex is trivially O(V*(V+E)). I also have depth limit k here and Wikipedia claims (in the page linked above) that running BFS with this constraint for every vertex will be O(V*E). Why is that? In the worst case when every vertex is in the "range" of k from every other vertex I'll have to search the entire graph V times, after all.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

There are two cases.

First. $V-1 \leq E$. Then $O(V \cdot (V + E))$ and $O(V \cdot E)$ are equivalent.

Second. $E < V-1$. Then graph is disconnected and the biggest component has size at most $E + 1$. The whole algorithm will consist of $V$ BFS runs each on the component which has at most $E + 1$ vertices and at most $E$ edges. So each BFS run will take $O(E)$ time and the whole algorithm - $O(VE)$.

Note: this reasoning does not depend on $k$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Simple and elegant, thank you. $\endgroup$
    – qalis
    Commented Apr 19, 2020 at 20:59
  • 1
    $\begingroup$ I like this but don't understand how you got to the intermediate claim of $O(E^2)$ -- after bounding the size of each component, doesn't $O(VE)$ follow directly from the fact that we perform $V$ BFS operations, each on a (sub)graph of size at most $E+1$ vertices and $E-2$ edges? The $O(E^2)$ claim seems to imply that arbitrarily many isolated vertices can be processed/ignored in constant time. $\endgroup$
    – j_random_hacker
    Commented Apr 20, 2020 at 17:35
  • $\begingroup$ @j_random_hacker Thank you, fixed it. Obviously, there can't be $O(E^2)$ because for graph consisting of only isolated vertices it will imply $O(1)$ algorithm. $\endgroup$
    – Vladislav Bezhentsev
    Commented Apr 20, 2020 at 18:30
  • $\begingroup$ Thanks, +1. Must try to remember this component size upper bound for the sparse case, feels like it could be useful. $\endgroup$
    – j_random_hacker
    Commented Apr 20, 2020 at 19:34

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.