8.2 Graph Search: From a Single Path to the Entire Network
Chapter 8 · Graph Search | Prerequisites: Graph Representation, Stack, and Queue | Next: Weighted Shortest Path. This lesson builds on DFS and BFS to explore connected components, topological sorting, bipartite graphs, and object graph copying.
Two Approaches
Both approaches will visit every reachable node from the starting point, but they differ in traversal order and the data structure used:
| DFS | BFS | |
|---|---|---|
| Data structure for pending nodes | Stack (last-in, first-out) | Queue (first-in, first-out) |
| Intuition | Go down one path to its end before backtracking | Expand outward in layers, one level at a time |
| Unweighted or equal-weight shortest path | Does not guarantee the shortest path | First discovery gives the minimum edge count |
| Common use cases | Reachability, cycle detection, topological ordering | Distance, level structure, shortest path in unweighted graphs |
Here, "shortest" means the fewest edges in an unweighted graph. If all weights are equal and nonnegative, a minimum-edge path also minimizes total weight. That conclusion does not extend directly to negative or unequal weights.
Complete Implementation
Input is an adjacency map {vertex: [neighbors...]}. Vertices appearing only in neighbor lists receive empty lists. Vertices must be hashable, with stable equality and hash behavior during traversal; None is also a valid vertex. Neighbor iterators are consumed, and the graph must remain unchanged during a call.
Convert the previous lesson's graph object g with {v: g.neighbors(v) for v in range(g.n)}. Maps can also name vertices directly with strings. DFS stores the unfinished neighbor iterator for each level on a stack. It follows each newly discovered neighbor immediately, matching recursive DFS on the same adjacency order. Each vertex is marked once when entered. Marking and pushing all neighbors at once can find reachable vertices, but need not preserve this DFS order.
from collections import deque
def _normalize(graph):
adjacency = {node: list(neighbors) for node, neighbors in graph.items()}
for neighbors in list(adjacency.values()):
for neighbor in neighbors:
adjacency.setdefault(neighbor, [])
return adjacency
def _require_start(adjacency, start):
if start not in adjacency:
raise KeyError(f"unknown start vertex: {start!r}")
def dfs(graph, start):
"""Iterative DFS matching recursive adjacency-list order."""
adjacency = _normalize(graph)
_require_start(adjacency, start)
discovered = {start}
order = [start]
stack = [iter(adjacency[start])]
while stack:
try:
neighbor = next(stack[-1])
except StopIteration:
stack.pop()
continue
if neighbor not in discovered:
discovered.add(neighbor)
order.append(neighbor)
stack.append(iter(adjacency[neighbor]))
return order
def bfs(graph, start):
"""Return reachable vertices in BFS discovery order."""
adjacency = _normalize(graph)
_require_start(adjacency, start)
discovered = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adjacency[node]:
if neighbor not in discovered:
discovered.add(neighbor)
queue.append(neighbor)
return order
def bfs_shortest_path(graph, start, target):
"""Return a minimum-edge path including both endpoints, or None."""
adjacency = _normalize(graph)
_require_start(adjacency, start)
if target not in adjacency:
return None
parent = {start: start}
queue = deque([start])
while queue:
node = queue.popleft()
if node == target:
break
for neighbor in adjacency[node]:
if neighbor not in parent:
parent[neighbor] = node
queue.append(neighbor)
if target not in parent:
return None
path = []
current = target
while True:
path.append(current)
if current == start:
break
current = parent[current]
path.reverse()
return path
def connected_components(graph):
"""Connected components of an undirected graph; for a directed graph, first specify whether weak or strong connectivity is intended."""
adjacency = _normalize(graph)
seen = set()
components = []
for start in adjacency:
if start in seen:
continue
component = []
queue = deque([start])
seen.add(start)
while queue:
node = queue.popleft()
component.append(node)
for neighbor in adjacency[node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
components.append(component)
return components
def topological_sort(graph):
"""Kahn algorithm; raise ValueError on cycles. Order need not be unique."""
adjacency = _normalize(graph)
indegree = {node: 0 for node in adjacency}
for neighbors in adjacency.values():
for neighbor in neighbors:
indegree[neighbor] += 1
queue = deque(node for node in adjacency if indegree[node] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adjacency[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(order) != len(adjacency):
raise ValueError("graph contains a directed cycle")
return order
def is_bipartite(graph):
"""Ignore edge directions; return False for an odd cycle or self-loop."""
adjacency = _normalize(graph)
constraints = {node: set() for node in adjacency}
for node, neighbors in adjacency.items():
for neighbor in neighbors:
constraints[node].add(neighbor)
constraints[neighbor].add(node)
color = {}
for start in constraints:
if start in color:
continue
color[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in constraints[node]:
if neighbor == node:
return False
if neighbor not in color:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False
return True
class GraphNode:
def __init__(self, value):
self.value = value
self.neighbors = []
def clone_graph(start):
"""Copy the reachable object graph, preserving cycles and shared neighbors."""
if start is None:
return None
copies = {start: GraphNode(start.value)}
queue = deque([start])
while queue:
original = queue.popleft()
for neighbor in original.neighbors:
if neighbor not in copies:
copies[neighbor] = GraphNode(neighbor.value)
queue.append(neighbor)
copies[original].neighbors.append(copies[neighbor])
return copies[start]
if __name__ == "__main__":
network = {
"A": ["B", "D"],
"B": ["A", "C", "F"],
"C": ["B"],
"D": ["A", "E"],
"E": ["D", "F"],
"F": ["B", "E"],
"G": [],
}
print("DFS:", dfs(network, "A"))
print("BFS:", bfs(network, "A"))
print("A to E:", bfs_shortest_path(network, "A", "E"))
print("Components:", connected_components(network))After execution, you should see:
DFS: ['A', 'B', 'C', 'F', 'E', 'D']
BFS: ['A', 'B', 'D', 'C', 'F', 'E']
A to E: ['A', 'D', 'E']
Components: [['A', 'B', 'D', 'C', 'F', 'E'], ['G']]The exact order of DFS traversal is not mathematically unique; changing the order of the adjacency list will yield different valid results. BFS may also have several shortest paths; this implementation returns the first discovered. An unknown start raises KeyError; an unknown or unreachable target returns None. Equal start and target return [start]. Reconstruction stops at the start vertex, so it does not confuse a valid vertex named None with an end marker.
Trace BFS
Group vertices by their minimum edge count from A:
Layer 0: A
Layer 1: B, D
Layer 2: C, F, EThe queue evolves as follows:
[A]
Remove A, add B and D -> [B, D]
Remove B, add C and F -> [D, C, F]
Remove D, add E -> [C, F, E]
No new vertices remain -> []E is first discovered from D, so reconstruction gives A→D→E. This uses one fewer edge than A→B→F→E. If edge costs differ, fewer edges need not mean a faster route.
The Python documentation defines collections.deque as a container with near-O(1) append and pop operations at both ends; list.pop(0) shifts subsequent elements and is therefore unsuitable for use as a BFS queue. See: collections.deque.
Complexity and Recursion Boundaries
Let the whole graph contain V vertices and E adjacency entries, and the reachable region contain Vr and Er. Assuming average constant-time hash access, the DFS/BFS traversal itself takes O(Vr+Er). Its discovery set, stack or queue, and order list use O(Vr) space. Every function here first calls _normalize, however, copying the whole graph in O(V+E) time and space. The full functions therefore have O(V+E) bounds even for an isolated start.
Connected components, Kahn sorting, and bipartite testing also process the whole graph in O(V+E) time. Including normalization, auxiliary space is of the same order. A path result adds O(Vr) space. General graph-search space includes the discovery set; tree height or a single layer's width alone does not account for it.
Recursive DFS works well for illustrating backtracking, but Python's recursion limit is platform-dependent and runtime-specific. You can check it using sys.getrecursionlimit(), do not memorize a fixed value. Setting it too high may cause the interpreter to crash. See: Python sys.getrecursionlimit. When input depth is uncontrolled, an explicit stack provides better risk management, though this does not establish a dogma that recursion is forbidden in production code.
Connected Components: Visit Each Separate Region
For directed graphs, we must first clarify the problem:
- Weakly connected: Is the graph connected if we ignore edge directions.
- Strongly connected: Within a component, can any two vertices reach each other via directed edges.
connected_components() requires an undirected graph: callers must supply both directions of every non-loop edge. It neither adds reverse edges nor validates symmetry. Applying it directly to directed graphs will yield results dependent on traversal direction, and does not equate to strongly connected components.
Topological Sorting: Prerequisites First
Task A waits for B, B waits for C, and C waits for A. This cycle prevents any task from starting first. Define each dependency edge to point from a prerequisite to the task that follows it. Topological sorting only applies to directed acyclic graphs (DAGs): for every edge u → v, ensure that u appears before v.
The Kahn algorithm repeatedly selects nodes with zero in-degree. If not all nodes are processed by the end, the remaining portion contains a cycle. When multiple nodes have zero in-degree at the same time, different choices yield different results, so the topological order may not be unique. A single chain has a unique order. Unprocessed vertices include a cycle and may also include vertices blocked downstream of it; the remaining set is not necessarily the set of vertices on cycles. Correctness should be verified by checking the relative ordering of each edge, not by rigidly adhering to a specific list. Official APIs explicitly state that topological sorting applies only to DAGs and fail when a cycle is detected: NetworkX topological_sort.
Bipartite Graphs: Edges Cross Between Groups
Two-coloring begins at any uncolored node, assigning the opposite color to adjacent nodes. The bipartite relationship is inherently undirected, on this page, every input edge is treated as an undirected "opposite-color constraint." As a result, the boolean answer does not depend on adjacency-key order. The two color labels themselves may be swapped. If two adjacent nodes end up with the same color, it indicates the presence of an odd-length cycle; self-loops, where a node belongs to both groups, will also cause failure. Each connected component of an unconnected graph must be individually validated. This approach aligns with established semantic implementations in mature libraries: NetworkX is_bipartite.
Why Graph Copying Requires Mapping
Object graphs may contain cycles or have two nodes sharing the same neighbor. Simply recursively creating new nodes would lead to infinite loops or accidentally duplicating shared nodes. copies[original node] = new node resolves both issues: previously seen nodes are not recreated, and shared references point to the same copy.
This copies nodes and neighbor lists, preserving neighbor order, duplicate edges, and self-loops. It only copies the value reference, so mutable payloads remain shared with the original graph. GraphNode uses default identity-based hashing and equality; two nodes with the same value remain distinct. For Vr reachable nodes and Er neighbor entries, time is O(Vr+Er), the auxiliary map and queue use O(Vr), and the new graph adds Θ(Vr+Er) output space.
Professional Quick Reference
- Ask about reachability? Use DFS or BFS.
- Query for the fewest edges with no weights or equal weights? Use BFS, and record
parent. - How many disconnected components exist in an undirected graph? Start a DFS or BFS from each vertex.
- Determine dependency order? First verify that the graph is directed and acyclic, then perform a topological sort.
- Can the graph be partitioned into two groups such that edges only cross groups? Perform two-coloring on each connected component.
- Input depth might be large? Check recursion limits; if needed, switch to an explicit stack implementation.
Search an Unweighted Graph
Both DFS and BFS must clearly define when a node is marked as discovered, otherwise cycles and shared predecessors will lead to redundant work. BFS guarantees the shortest path in terms of number of edges only for unweighted or equally weighted graphs; connected components, topological sorting, and bipartite graph detection each require additional assumptions, such as undirected graphs, DAGs, or color constraints in undirected graphs. The first step in any graph algorithm is never simply plugging in a template; it's about clearly specifying the graph's direction, edge weights, and the problem's requirements.
Edges now begin to carry different costs. The next lesson is Dijkstra, Bellman–Ford, and Shortest Paths on DAGs.