There are lots of places in the course where the code is being shown like a Git patch rather than a block of code. It’s showing a diff
I believe that’s the point to show a difference between tree and graph implementations of the same algorithm.
Slide #7 should say “Add 4’s neighbors to stack” not “Add 2’s”
Why and how are you removing 1 from the stack in slide#7, I thought this was a stack. LIFO?
I think it wasnt supposed to be in the stack to begin with. Honestly this course is so sloppy bruh
Formatting is off on this page.
Please fix it as I can see git file difference here
I agree, solution is using recursion and slide is showing stack. Even though recursion uses stack behind the scene but both work a little differently, in recursion not all neighbors are put in stack (for ex. think of a graph with one node connecting to 1000s of other nodes and other nodes has only this node as neighbor, in this example stack solution will have all the nodes put in stack consuming a lot memory vs recursion will have at max two stack frames at any time)
Why is the code showing as git diff ?
It is a diff between the DFS template from the Depth First Search section and the DFS from this graph section.
Why is complexity O(V + E) but not O(V) ?
O(|E|) varies between O(1) to O(|V|^2). In the best case there could only be one edge in the entire graph, and in the worse case where each vertex is connected to every other vertex, edge count is n^2 vertex. So we don’t know whether |V| or |E| is larger and therefore include both terms.
Please clarify how |E| is n ^2 ? If I have graph as follows
Then I have 3 vertices how are the edges 3 ^2 = 9 ?
For each vertix x, draw a path from x to every other node in the graph and a path to x itself. Each node will have 3 paths. Hence the number of paths will be 3*3 = 9.