Why is the time complexity O(V+E) in depth-first search of graphs implemented as linked lists?

           A
         / | \
        B  |  D -- E
         \ | /     |
           C ------+

If you have a graph implemented as a linked list, you must call the DFS function n times to visit n vertices, and each call must move between nodes in the linked list at least a certain number of times to find the next vertex to visit.

If the number of times this node moves is m, the time complexity should be O(nm).In practice, O (V+E) is the number of vertices V plus the number of edges E.

How was O(V+E) calculated?

algorithm

2022-09-22 20:20

1 Answers

The number of nodes N = the number of vertices V, and the number of movements is the number of edges, so O(V+E). O(nm) means that the loops of n and m are overlapped.


for(int i=0; i<N; i++)
{
    for(int j=0; j<M; j++)
    {
       // // do something
    }
 }

2022-09-22 20:20

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656