How BFS Works

Adding an edge is an if-else on whether the source vertex already has a neighbor list. If it does, the new neighbor appends to the existing list. If it does not, the method creates a new one-element list. The doctest verifies both branches: the first add_edge(0, 1) call creates vertex 0's list, and the duplicate add_edge(0, 1) call in the BFS doctest later tests that a second identical edge appends rather than overwrites. The BFS method must therefore handle duplicate neighbors in the adjacency list, which is why the visited set is checked before enqueuing rather than after dequeuing. The simplicity of this two-branch method is intentional: graph construction stays out of the search logic, and the search only reads self.vertices.

The BFS traversal rests on three structures whose roles are distinct and non-interchangeable. The visited set on line 54 prevents a vertex from being processed more than once; it is checked before enqueuing, not after dequeuing, which is why the self-loop (vertex 3 to vertex 3) in the doctest does not cause an infinite loop. The queue on line 57 is Python's Queue, a FIFO structure; using a stack here would produce depth-first traversal instead. The self.vertices dict is the adjacency map the add_edge method built. The loop invariant is that every vertex in the queue has already been added to visited, so the adjacency scan only enqueues genuinely new vertices. The function returns the visited set rather than a list because the doctest uses sorted() to get deterministic output; traversal order depends on insertion order in the adjacency list, not alphabetical order.

The doctest is short but each edge is chosen deliberately. add_edge(0, 1) appears twice to test that the adjacency list accumulates duplicates without error and that BFS still visits vertex 1 exactly once. add_edge(2, 0) creates a cycle back to vertex 0, which would loop forever if the visited set were not checked before enqueuing. add_edge(3, 3) creates a self-loop, which is the hardest case: vertex 3 has itself as a neighbor, so a traversal without a visited check would enqueue vertex 3 immediately after dequeuing it. The assertion uses sorted(g.bfs(2)) because bfs returns a set and set ordering is not guaranteed. Starting from vertex 2 rather than 0 shows that BFS does not require the lowest-numbered vertex as the source and still reaches every reachable vertex in a strongly connected subgraph.

This block has two design choices worth calling out. testmod(verbose=True) on line 77 prints each doctest as it runs with its pass/fail result, making the file self-documenting when invoked directly. The last line uses assert rather than print, so a wrong BFS result raises a visible AssertionError rather than producing silent output. The print_graph() call on line 87 prints the adjacency list in a readable format; the four commented lines below it show exactly what the output looks like, which is a documentation convention the repository uses in several graph files. The graph built here is a subset of the one in the BFS doctest: it excludes the duplicate (0, 1) edge but keeps the cycle and the self-loop, so the assert is equivalent to verifying the same four-vertex reachability.

The BFS loop body is the place to see what separates BFS from DFS by reading the code rather than a diagram. The structure here is a FIFO drain: queue.get() removes the oldest entry, and queue.put() appends the newest. The effect is that vertices added during expansion of layer d wait behind all existing layer-d entries and are processed only after every layer-d vertex is done, giving the layer-by-layer guarantee. The DFS file at graphs/depth_first_search.py replaces Queue with a plain list used as a stack, calling stack.pop() to take the most recently added entry. Both share the same visited-set check; the single structural difference is FIFO versus LIFO. That one swap changes shortest-path guarantee to depth-first backtracking.