Build a Dependency ResolverStep 2 of 5

Breadth-first search

12345

Step 2: Breadth-first search

Now that we can build the graph, we need to explore it. Breadth-first search (BFS) visits a start node, then all of its direct dependencies, then their dependencies, level by level. Package managers use this style of walk to answer "what does this package reach?" one ring at a time.

Implement bfs(start) returning the list of nodes in BFS order:

  • Start from start and visit neighbors in insertion order.
  • Never visit a node twice.

Use a queue (collections.deque is imported for you). Mark a node as seen when you enqueue it so it is not queued again.

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.bfs("a") -> ["a", "b", "c", "d", "e"]
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):
        """Return nodes reachable from start in breadth-first order.

        Visit neighbors in insertion order and never repeat a node.
        """
        # TODO: use a deque as a queue. Track seen nodes, append each node to
        # the result when it is dequeued, and enqueue unseen neighbors.
        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