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.

$\endgroup$
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$.

$\endgroup$
4
  • $\begingroup$ Simple and elegant, thank you. $\endgroup$ – qalis Apr 19 '20 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 Apr 20 '20 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 Apr 20 '20 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 Apr 20 '20 at 19:34

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.