Introduction
Adrian Sampson shows how to develop depth-first search (dfs) and breadth-first search (bfs). Both algorithms are used to traverse a graph, "visiting" each of its nodes in an orderly fashion. He assumes you are familiar with the idea. He also figures out the time complexity of these algorithms. Finally, he shows you how to implement a DFS walk of a graph.
DFS (depth-first search)
In this 2.45 minute video, we develop an abstract version of a recursive dfs procedure, with the specification shown below. Read it here: dfs01develop.pdf
/** Visit every node reachable along a path of unvisited nodes from node u.
Precondition: u is not visited. */
public static void dfs(Node u)
Now, on a blank sheet of paper, write the specification of dfs and then develop dfs yourself. We urge you to first draw the outline of the graph as done in the video, for that will help you develop the procedure. Compare your result to the procedure we developed, note differences, and do the task again until you understand the development and can do it at any time.
How to test whether a node has been visited?
We left the notion of visiting and testing whether a node has been visited abstract. Figure out how to implement the set of visited nodes. You can add parameters to the method if you want.
DFS without the precondition
We ask you to develop an abstract version of the dfs procedure that does not have the precondition that u is not visited. The specification is given below. We will use our own solution in the next video.
/** Visit every node reachable along a path of unvisited nodes from node u. */
public static void dfs1(Node u)
DFS time complexity
We determine the exact number of times each statement of procedure dfs1 is executed. The number of recursive calls turns out to be very large, and we show how to eliminate most of them (3.25 minutes). Read it here: dfs02analyze.pdf
Iterative dfs
In just over 4 minutes, we develop a non-recursive version of dfs. It maintains a stack of nodes, akin to the stack of frames for incompleted calls on the recursive dfs procedure. We show two ways of implementing the stack. Read it here: dfs03dfsloop.pdf
Iterative bfs
WIn just under 1 minute and 15 seconds, we define breadth-first search (bfs) and show how to change the iterative dfs procedure into an iterative bfs procedure. It's easy --just replace the stack by a queue. Read it here: dfs04bfs/pdf
While one can write bfs recursively ---recursion and iteration are equally powerful--- it is awkward, and no one does it, practically speaking.
Dfs walk
In some situations, we want a graph traversal that is like a walk using a city map, simulating a walker always walking from one node along an edge to another node. In under 3.5 minutes, we show that using a breadth-first walk would be extremely inefficient, and we implement a depth-first search walk. Read it here: dfs05dfsWalk.pdf