Algorithms For Dummies

  Reconnecting the Dots 

     179

Stack is: ['B', 'C']

Processing C

Adding D to the stack

Adding E to the stack

Stack is: ['B', 'D', 'E']

Processing E

Adding F to the stack

Stack is: ['B', 'D', 'F']

Processing F

Stack is: ['B', 'D']

Processing D

Stack is: ['B']

Processing B

DFS: ['A>C', 'C>E', 'E>F', 'C>D', 'A>B']

The first line of output shows the actual search order. Note that the search begins 

at the root, as expected, but then follows down the left side of the graph around to 

the beginning. The final step is to search the only branch off the loop that creates 

the graph in this case, which is D.

Note that the output is not the same as for the BFS. In this case, the processing 

route begins with node A and moves to the opposite side of the graph, to node F. 

The code then retraces back to look for overlooked paths. As discussed, this behav-

ior depends on the use of a stack structure in place of a queue. Reliance on a stack 

means that you could also implement this kind of search using recursion. The use 

of recursion would make the algorithm faster, so you could obtain results faster 

than when using a BFS. The trade-off is that you use more memory when using 

recursion.

When your algorithm uses a stack, it’s using the last result available (as contrasted 

to  a  queue,  where  it  would  use  the  first  result  placed  in  the  queue).  Recursive 

functions produce a result and then apply themselves using that same result.  

A  stack  does  exactly  the  same  thing  in  an  iteration:  The  algorithm  produces  a 

result, the result is put on a stack, and then the result is immediately taken from 

the stack and processed again.