Graph DFS Generator

Lazily traverse a graph depth-first with an explicit stack and no recursion.

generators dfs graph iterators

Write a generator function `dfs_generator(graph, start)` that yields vertices in depth-first order starting from `start`. The graph is represented as a dictionary mapping each vertex to a list of its neighbors (vertex keys are always strings, neighbor lists may contain strings). The order of neighbors matters: they are visited in the given order. Use an explicit stack to avoid recursion. The traversal should visit each vertex exactly once; vertices already visited are skipped. For each popped vertex, push its unvisited neighbors onto the stack in reverse order so that they are popped in the original neighbor order. Do not use function recursion; a simple loop is required. The `start` vertex is always a string. All vertices and neighbors are strings. The graph may contain cycles and disconnected vertices, but `start` is guaranteed to be a key in the dictionary.

Constraints

- The graph has at most 1000 vertices and 5000 edges.
- All vertex keys and neighbor values are strings and hashable.
- The start vertex is guaranteed to be a key in the graph.
- The function must be a generator (using `yield`).

Example

>>> graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
>>> list(dfs_generator(graph, 'A'))
['A', 'B', 'D', 'C']
>>> list(dfs_generator(graph, 'C'))
['C']

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a stack initialized with `start` and a set to track visited vertices.

When processing a vertex, yield it and then push its unvisited neighbors in reverse order.

Remember to mark a vertex as visited when you push it onto the stack to avoid duplicate pushes.

The generator should be lazy, yielding one vertex at a time as the loop runs.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.