Build a Dependency ResolverStep 3 of 5

Depth-first search

12345

Step 3: Depth-first search

Depth-first search (DFS) dives all the way down one dependency chain before backing up to try the next. This is the traversal that build tools use to walk a full dependency subtree, and it is the backbone of topological sorting.

Implement dfs(start) returning nodes in DFS preorder: record a node the moment you first reach it, then recurse into its neighbors in insertion order. Never visit a node twice.

g.add_edge("a", "b")
g.add_edge("a", "c")
g.add_edge("b", "d")
g.add_edge("c", "d")
g.add_edge("c", "e")
g.dfs("a") -> ["a", "b", "d", "c", "e"]

Notice how this differs from BFS on the same graph: DFS follows a -> b -> d to the bottom before returning to explore c.

Hints
Starter code
from collections import deque


class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        if u not in self.adj:
            self.adj[u] = []
        if v not in self.adj:
            self.adj[v] = []
        self.adj[u].append(v)

    def nodes(self):
        return list(self.adj.keys())

    def neighbors(self, u):
        return self.adj.get(u, [])

    def bfs(self, start):
        seen = {start}
        queue = deque([start])
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nb in self.adj.get(node, []):
                if nb not in seen:
                    seen.add(nb)
                    queue.append(nb)
        return order

    def dfs(self, start):
        """Return nodes reachable from start in depth-first preorder.

        Record a node when first reached, then recurse into its neighbors in
        insertion order. Never repeat a node.
        """
        # TODO: keep a seen set and an order list. Write a helper that returns
        # early if a node was seen, otherwise records it and recurses into
        # each neighbor. Call the helper on start, then return order.
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step