I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems very easy to grasp for me so, lets coming to the point there was this section on his notes where he tells:
Traversing connected graphs:
The generic graph traversal algorithm stores a set of candidate edges in some data structure that I’ll call a “bag”. The only important properties of a “bag” are that we can put stuff into it and then later take stuff back out. A stack is a particular type of bag, but certainly not the only one. Here is the generic traversal algorithm:
Traverse(s):
put (∅,s) in bag
while the bag is not empty
take (p, v) from the bag (?)
if v is unmarked
mark v
parent(v) ← p
for each edge vw (†)
put (v, w) into the bag (??)
Seems fine and understandable to me till now then, he goes on to explain the running time of these algorithm which for me is the most important part:
The exact running time of the traversal algorithm depends on how the graph is represented and what data structure is used as the ‘bag’, but we can make a few general observations. Because each vertex is marked at most once, the for loop (†) is executed at most V times. Each edge uv is put into the bag exactly twice; once as the pair (u, v) and once as the pair (v, u), so line (??) is executed at most 2E times. Finally, we can’t take more things out of the bag than we put in, so line (?) is executed at most 2E + 1 times.
And now the bells ring, the two confusing part for me is:
- Why line(?) is executed 2E + 1 times? why not 2E? as there are 2E edged, from where this extra 1 is coming from?
- The most confusing part now is the statement about line(†). Suppose I assume that he is correct.
Now, lets go further:
Let’s first assume that the graph is represented by a standard adjacency list, so that the overhead of the for loop (†) is only constant time per edge.
• If we implement the ‘bag’ using a stack, we recover our original depth-first search algorithm. Each execution of (?) or (??) takes constant time, so the algorithms runs in O(V + E) time . If the graph is connected, we have V ≤ E + 1, and so we can simplify the running time to O(E). The spanning tree formed by the parent edges is called a depth-first spanning tree. The exact shape of the tree depends on the start vertex and on the order that neighbors are visited in the for loop (†), but in general, depth-first spanning trees are long and skinny
According to me he took the statement (?) and (†) which corresponds to 2E+1 and V respectively to get the running time of the algorithms(I am still hand waving).
The scenario becomes more confusing as he explains what happens when we use adjacency matrix instead of an adjacency list he states:
If the graph is represented using an adjacency matrix instead of an adjacency list, finding all the neighbors of each vertex in line (†) takes O(V) time. Thus, depth- and breadth-first search each run in O(V^ 2 ) time, and ‘shortest-first search’ runs in O(V^2 + E log E) = O(V^2 log V) time.
I agree that its one of the simplest example of the running time and I understand most part of it but the major confusing part for me is the statement including the for loop. Till date I have never included for the loop in the algorithm analysis but the statement inside the for loop for some reason I am not able to digest the reasoning involving the for loop in both the cases.
I have tried to read and understand the statement since couple of days but no success. I am not studying in the university hence I am of my own and no one discuss that's why some may think that my post is so long but maybe I wanted to discuss my doubt clearly.
PS: Correct me if I am missing any mental model or analogy regarding the for loop because right now I am staring it blankly and nothing coming to my mind. I am sound stupid but I need to understand graph theory and I have made up my mind for it.
Here is the relevant lecture note:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/18-graphs.pdf