Instructions:
Choose a graph and a source node, then click the buttons (or press the
← and → keys) to step through a depth-first search.
Each step ends when dfs is called or returns.
As in lecture, each node is
undiscovered,
pending, or
visited,
and a node's neighbors are produced in sorted order.
The tree of function calls shows the nested calls to dfs,
where dfs(u) is short for dfs(graph, u, status).
Each call is indented under the call that made it. The calls that haven't
returned yet are pending; they are
the call stack. The calls that have returned are grayed out. The call that is running is circled, both in the graph and in
the tree, where its text is also purple, and the edges it explores are drawn in bold.
Under Options, you can run a full DFS, or step through one edge at a
time.
Check Start and finish times to show the clock above the graph, and
each node's [start, finish] times both above the node in the
graph and next to its call in the tree. The clock goes up by one whenever a
node is marked pending or visited; the demo shows the tick just after the
node changes color.