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

Asked

Viewed 339 times

1

I need to show that the cost to know if there is a path between two vertices v and w is O(n²). For this I can make a BFS in a graph, only, 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 make the graphic representation, showing the dominating functions asymptotically.

c++

1 answer

1


That depends...

If you are using a list of adjacencies to represent the graph, the search algorithm in width (BFS) will have complexity O(V+A) being V the number of vertices and A the number of edges.

This is because each vertex will be visited once and will be marked, ie 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 be executed 2*A times, because the sum of the number of edges of each vertex gives 2 times the total number of edges.

Therefore you will run V+2A iterations in your code, but as in big-O notation constants are despised 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 on all vertices to look at the matrix and know whether the vertex is a neighbor or not.

  • Thank you very much Sérgio! Now I understand. You know what a graphic representation of O(n+m will look like)?

  • I don’t know, I think the best form of representation will depend on the case. I would put the y-axis as the number of operations and the x-axis as n+m so it would be a linear graph.

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.