0% completed
Incorrect Representation of Stack & Incorrect Example Of Graph
davemednikov
Feb 14, 2024
Both Step-by-step illustrations of DFS on this page have issues.
For the first graph, containing the vertices [0, 1, 2, 3, 4], the visual representation of the stack behaves like a queue.
When vertex 0 is visited, vertices [1, 2, 3] are pushed onto the stack. On the next turn, vertex 1 is "popped" from the stack and moved to the visited list. The visual representation looks like a queue, where the item with index 0 is popped. It effectively looks like vertex 1 was removed using popleft() instead of pop().
A proper visual representation of the stack would pop vertex 3, since it is the furthest-to-the-right element in the stack. For this entire course queues and stacks have been read from left-to-right.
The graph of the tree-like structure with vertices [A, B, C, D, E, F] is also incorrect. Step 12 says Node F has no unvisited neighbors, so we backtrack to node E. This is clearly false, as in the graph illustration, vertex C is a neighbor of vertex F, with an edge clearly connecting them. It appears that vertex C should be pushed to the stack when vertex F is visited. If the purpose of this section is to visualize how the stack works when popping all visited nodes, all the way to the first vertex (A) then there should not be an edge connecting vertices F and C
14
0
Comments
Wanru Xia2 years ago
Also, When vertex 0 is visited, we should only push one node either1/2/3 onto the stack
mariana.lopez.jaimez 2 years ago
Thank you! I was wondering about vertex C in the given example.
Miguel a year ago
-
I agree with your gripe about the representation of a stack in the first example. The clearest way to represent it would be bottom to top, but I can see why space did not permit.
-
Step 12 is not wrong.
Cwas added tovisitedback whenAwas processed. In t...
On this page