Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

Question

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:

1. Why line(?) is executed 2E + 1 times? why not 2E? as there are 2E edged, from where this extra 1 is coming from?
2. 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

Answer 1

I suspect that our reference question contains all you need, but let me address your questions.

Why line(?) is executed 2E + 1 times? why not 2E?

We start with $(\_, s)$ in the bag -- that's a virtual edge not in the tree, hence we get $2|E| + 1$.

the for loop (†) is executed at most V times.

The most confusing part now is the statement about line(†)

Are we clear that the meaning is "we get to that loop exactly $|V|$ times", not "there are $|V|$ iterations of that loop in total"?

so the algorithms runs in O(V + E) time .

(I am still hand waving)

He's just adding up things. JeffE applies the execution count technique. You can make that explicit by writing the number of executions next to each line; then add up the figures (which gives the correct result up to a constant factor assuming that each line takes time $O(1)$).

The scenario becomes more confusing as he explains what happens when we use adjacency matrix instead of an adjacency list

You can approach this by unfolding (†) for each specific graph representation, then apply the method as above.

---

Meta comment: This analysis is a good example for what I dislike in many textbook analyses. It combines proof of correctness and running-time analysis in a handwaving way -- note how much smoother the analysis can go if we first prove that each node gets visited exactly once (for a reasonable definition of what "visit" means)! Then, the algorithm is not even given in as much detail as is necessary to derive the cost at the level of precision we want to, and we expect the reader to fill the gaps.
That said, it's certainly one of the better write-ups with these properties. I'm really criticizing the culture of the field, not the author.