How DFS Works

The graph format here is simpler than the Graph class in breadth_first_search.py: a plain dict whose keys are vertex names (strings here, not integers) and whose values are neighbor lists. Passing the graph as a dict rather than constructing a class instance means the caller controls the graph layout entirely. The two doctests sidestep traversal-order nondeterminism by checking membership rather than equality: all(x in output_G for x in ...) asserts that every vertex returned by DFS is in the expected set of all seven vertices. Running from vertex A and from vertex G checks that any starting point in a connected graph reaches every other vertex. The graph contains a self-loop (D lists D as a neighbor) and a back edge (B to A), both of which the visited set must handle.

Line 20 is the most compact initialization in the file: set(start) produces a one-element set only because every vertex here is a single character (set('AB') would split into {'A','B'}), and [start] is a one-element list serving as the stack. Initializing explored with the start vertex before the loop handles the self-loop case: if the start vertex has itself as a neighbor, the check on line 29 blocks it from being pushed again. The stack.pop() on line 23 removes the last element (LIFO), which is the defining difference from BFS. The reversed(graph[v]) on line 28 is a deliberate ordering choice: pushing neighbors in reversed order means the first neighbor in the adjacency list ends up on top of the stack and is therefore explored first, preserving the left-to-right expansion order. Without reversing, the rightmost neighbor would be visited first.

The module-level G dict on lines 34 through 42 is the same graph used in the doctest. Defining it at module level rather than inside __main__ means it is available to any importer and matches the dict the doctest constructs inline, so a reader can compare them side by side. The graph is undirected in spirit but represented as a directed adjacency list: vertex A lists B, C, D as neighbors, and vertex B lists A back. Vertex D lists D, the self-loop the doctest relies on. The __main__ block runs doctest.testmod() first, which validates the two membership assertions in the docstring, then prints the actual traversal result of depth_first_search(G, "A"). Because sets are unordered, the printed output will vary across Python versions and runs; the doctest avoids this by not asserting the set contents directly.

The code comment on lines 25 through 27 is explicit about what distinguishes this loop from BFS. The two numbered differences the comment names are: (1) pop from the last position instead of the front, and (2) add adjacent elements to the frontier without marking them as explored at that moment. The BFS implementation in breadth_first_search.py uses queue.put() and queue.get() with a Queue object; this file uses stack.append() and stack.pop() on a plain list. Both check the visited structure before adding to the frontier. Both return a set of all reachable vertices. The difference is which vertex each picks next: BFS picks the oldest frontier member (shortest distance first), DFS picks the newest (deepest path first). That single choice determines whether the traversal guarantees shortest paths or exhaustive depth-first coverage.