fiery
June 30, 2013, 10:56am
1
It is just that i am unable to understand how complexity(time) of bfs/dfs are O(v+e).
why not O(v*e)???since most of the times i have seen we just multiply inner loop and outer loop iterations and compute complexity so what is the difference we are having here.

P.S: I have already seen link: http://stackoverflow.com/questions/6850357/explanation-of-runtimes-of-bfs-and-dfs
and CLRS but didn’t get it.

I think u didn’t go through the link contain correct explaination why the time complexity of dfs and bfs is O(v+e) hope this help

DFS(analysis):

*Setting/getting a vertex/edge label takes O(1) time

*Each vertex is labeled twice

->once as UNEXPLORED

->once as VISITED

*Each edge is labeled twice

->once as UNEXPLORED

->once as DISCOVERY or BACK

*Method incidentEdges is called once for each vertex

*DFS runs in O(n + m) time provided the graph is represented by the adjacency list structure

*Recall that Σv deg(v) = 2m

BFS(analysis):

*Setting/getting a vertex/edge label takes O(1) time

*Each vertex is labeled twice

–>once as UNEXPLORED

–>once as VISITED

*Each edge is labeled twice

–>once as UNEXPLORED

–>once as DISCOVERY or CROSS

*Each vertex is inserted once into a sequence Li

*Method incidentEdges is called once for each vertex

*BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure

*Recall that Σv deg(v) = 2m

2 Likes

have u gone through this link …i think it is explained properly!!!

u can see this link also…it explains the algorithms with their complexities…hope it helps…

1 Like