Why is the complexity cost of a BFS O (n + m)?

Question

Why is the complexity cost of a BFS O (n + m)?

Navigation

#1 by (1 votes)

1

I need to show that the cost to know if there exists a path between two vertices v and w is O (n²). For this I can do a BFS in a graph, but, the cost of a bfs is O (n + m), but I do not understand why it has this "m", and also do not know how to do the graphical representation, showing the functions dominating asymptotically.

c++

asked by anonymous 12.08.2016 / 22:35

1 answer

"Timeout waiting for task." when trying to click webview button with espresso android AJAX request for PHP (CodeIgniter) does not return values

score 1 · Accepted Answer

That depends ...

If you are using an adjacency list to represent the graph, the BFS algorithm will have complexity O (V + A) where V is the number of vertices and A is the number of edges.

This is because each vertex will be visited once and will be marked, that is, complexity V. For each vertex you should check all your neighbors to know which ones are already marked. The number of neighbors is the number of edges that it is connected to. If you do this for all vertices this part of the code will run 2 * Sometimes, because the sum of the number of edges of each vertex gives 2 times the total number of edges.

So you will run V + 2A iterations in your code, but as in big-O notation the constants are neglected you would have complexity O (V + A).

If you are using an adjacency matrix to represent your graph, the algorithm will have complexity O (V²). This is because for each vertex you will have to iterate in all the vertices to look in the matrix and to know if the vertex is a neighbor or not.