1

I'm trying to implement BFS and DFS in Java as a generic algorithm. I'm writing a method getComplexity() that returns the worst case complexity of the algorithm as a string. In DFS (and BFS), each node in the graph can only be visited once. In the worst case, each node is visited only once. Hence, why is the complexity of these algorithms O(V+E) instead of O(V)? Here V is the number of nodes (or vertices) and E is the number of edges.

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
user2841060
  • 21
  • 1
  • 3
    Each node is visited once, each edge is traversed once. Hence O(V+E). – Aurand Oct 03 '13 at 03:55
  • 1
    This doesn't seem to be a duplicate to me. The OP in the question you posted understands why it is (v1 + e1 + v2 + e2 ...). But here, the OP is asking why this is true – Cricketer Oct 03 '13 at 03:58

2 Answers2

5

Tree traversal (BFS and DFS) is O(V + E) because each edge must be traversed exactly once and each node must be visited exactly once. Tree traversal is often an abstraction that helps give us a view on a problem. In most simple cases, both V and E are trivial operations, however this is not always the case and the efficiency of V could be radically different from E. For instance, traversing an edge could be as simple as following a pointer, or it might require you to fetch data from a remote host over a network (possibly involving an expensive database query). Visiting a node could be as simple as setting a boolean value, or it could involve performing some expensive computations on the data at that node.

O(V + E) reminds us that we must take into consideration both the complexity of visiting nodes and of traversing edges when we reason about the overall complexity of traversing a tree.

Aurand
  • 5,487
  • 1
  • 25
  • 35
  • Care to explain the down vote? – Aurand Oct 03 '13 at 04:14
  • I don't think differentiating between pointer following and external database queries has anything to do with the abstract big-Oh of the algorithm, much less setting a boolean value versus doing expensive computation. These are constant factors – torquestomp Oct 03 '13 at 04:17
  • 2
    @torquestomp I thought a concrete example would help to demonstrate why V != E. If V = E. O(V + E) = O(2V) and in big-Oh O(2V) simplifies to O(V) since in any tree the number of edges is equal to the number of nodes - 1. – Aurand Oct 03 '13 at 04:27
1

Because in general graph, E (i.e., the number of edges) can be as large as V*(V-1)/2 (for complete graph), which is in the order of V^2. So we can't just ignore the fact that we need to check each edge (for the purpose of finding unvisited nodes), since that checking might cost more (as I said, it can be V^2) than the cost to visit each node (which is always V).

justhalf
  • 8,960
  • 3
  • 47
  • 74