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 Ill 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 cant 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:Lets 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  skinnyAccording 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
Understanding Jeff Erickson's analysis of a basic tree traversal algorithm
algorithms;graphs;algorithm analysis;runtime analysis;graph traversal