Why does the time complexity of DFS and BFS depend on how the graph is presented?

Question

The website http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html describes that when an adjacency list is used, DFS and BFS have O (V + E) complexity and if an adjacency matrix is ​​used , complexity O (V ² ). Why is this?

Answer 1

In both cases, the execution time depends on how long it takes to iterate over the outgoing edges of a given node. Using the adjacency list, the execution time is directly proportional to the number of outgoing edges. Since each node is visited once, the cost is the number of nodes plus the number of edges, which is O (m + n). With the adjacency matrix, the time required to find all outgoing edges is O (n), since all n columns in a row for a node must be checked. Summing over all n nodes, this is obtained for O (n ² ).

Hope this helps!

Answer 2

You should notice that for studying each vertex of the time necessary for studying, it is equal only to c * x, where x is the uncertainty of the vertex. Since we are interested in general complexity, the total time will be c1 * x1 + c2 * x2 ... cnxn for n nodes. Taking max (ci) = d, we see that the total time is <= d (the sum of the values ​​of all the vertices) = d * 2m = O (m). we calculated the time not for one vertex, but for all vertices taken together. But the enqueuing operation takes O (n) time, so totall O (n + m).

Answer 3

The time complexity for DFS and BFS can be calculated as follows:

Iterate over each vertex once and the corresponding incident edges , so the total time complexity will be ->

Time complexity = v1 + (incident_edge on v1) + v2 + (incident_bound on v2) + ...... + vn + (incident_bound on vn)

Now it can be rearranged as → (v1 + v2 + v3 + ..... vn) + (incident_ji on v1 + incident_ji on v2 + ..... incident_ji on vn)

Thus, the total complexity of the time would be = (v1 + v2 + v3 + ..... vn) + (incident_ji on v1 + incident_ji on v2 + ..... incident_ji on vn)

(v1 + v2 + ... + vn) = V or n (total number of vertices)

To represent an adjacency list :

(hedge incident on v1 + hedge incident on v2 + ..... hedge incident on vn) = E (total number of edges)

Thus, for the adjacency list presentation time, the time complexity will be O (V + E)

To represent an adjacency matrix :

To visit the neighbors of the corresponding node (row), we need to iterate over all the columns for a particular row, which is V

So, (incident_edge on v1 + incident_edge on v2 + ..... incident_edge on vn) = V + V + .... Vth time V) = V * V

So the time complexity will be O (V + V ^ 2) = O (V ^ 2)