The Project | About Us | Contribute | Donations | License

HOME

We now have Rutalia's urban network in memory as an adjacency list. The natural question is: how do you traverse it? Almost everything we will do with graphs in this module — shortest paths, flow, matchings — rests on two fundamental forms of exploration: breadth-first search (BFS), which advances layer by layer like an expanding wave, and depth-first search (DFS), which plunges down one path until it is exhausted before backtracking. With just these two tools we will answer real operational questions for Rutalia: how many segments away is the farthest delivery point, which zones are cut off if roadworks close a street, and in what order the warehouse tasks must be executed.

BFS: level-by-level exploration with a queue
Distances in edges and path reconstruction with parent
DFS: recursive and iterative
BFS vs DFS comparison table
Cycle detection
Connected components: BFS versus the union-find of 01-04
Topological sort in DAGs: Kahn's algorithm
Applications in Rutalia: street closures and eccentricity

BFS: level-by-level exploration with a queue

BFS starts from a source node and visits all its neighbors first (level 1), then their neighbors (level 2), and so on. The structure that enforces this order is a FIFO queue: nodes are processed in the same order in which they are discovered.

from collections import deque

# Canonical graph of Rutalia (03-01): {node: {neighbor: minutes}}
NETWORK = {
    "ALM": {"RIO": 3, "MER": 4, "EST": 7, "CEN": 12},
    "MER": {"ALM": 4, "CEN": 5, "UNI": 6},
    "EST": {"ALM": 7, "UNI": 3, "IND": 9},
    "UNI": {"MER": 6, "EST": 3, "CEN": 8, "HOS": 5},
    "RIO": {"ALM": 3, "CEN": 6, "PAR": 8},
    "CEN": {"ALM": 12, "MER": 5, "UNI": 8, "RIO": 6, "HOS": 4},
    "IND": {"EST": 9, "HOS": 6},
    "HOS": {"UNI": 5, "CEN": 4, "IND": 6, "PAR": 7},
    "PAR": {"RIO": 8, "HOS": 7},
}

def bfs(graph, source):
    """Returns (dist, parent): distance in EDGES from source and the parent tree."""
    dist = {source: 0}
    parent = {source: None}
    queue = deque([source])
    while queue:
        u = queue.popleft()             # FIFO: oldest one out first
        for v in graph[u]:
            if v not in dist:           # not discovered yet
                dist[v] = dist[u] + 1   # one layer farther than u
                parent[v] = u
                queue.append(v)
        # the weights (minutes) are IGNORED on purpose: BFS counts segments
    return dist, parent

dist, parent = bfs(NETWORK, "ALM")
print(dist)
# {'ALM': 0, 'RIO': 1, 'MER': 1, 'EST': 1, 'CEN': 1,
#  'PAR': 2, 'UNI': 2, 'IND': 2, 'HOS': 2}

Key points in the code:

We mark a node as discovered when enqueueing it, not when dequeueing it. If it were marked late, the same node could enter the queue several times.
dist[v] = dist[u] + 1 works because the queue processes levels in order: when we pop u, every node at a smaller distance has already come out. This is the central guarantee of BFS: in unweighted graphs (or with all edges equal), dist[v] is the length of the shortest path in number of edges.
Complexity: each node enters and leaves the queue once, and each edge is examined twice (once per endpoint): O(n + m) with an adjacency list. With a matrix it would be O(n²) — another reason behind the choice made in 03-01.

Immediate operational reading: from the Warehouse, the whole city is at most 2 segments away. The eccentricity of ALM is 2. But careful: "2 segments" does not mean "little time" — we will see that at the end.

Distances in edges and path reconstruction with `parent`

parent stores, for each node, the node from which it was discovered. That dictionary defines a BFS tree rooted at the source, and lets us reconstruct the shortest path by walking backwards — the same reconstruction technique we used in the DP of 01-03:

def reconstruct(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]    # step back towards the source
    return path[::-1]              # it was backwards

print(reconstruct(parent, "HOS"))   # ['ALM', 'CEN', 'HOS']

BFS proposes going to the Hospital along the direct avenue: ALM→CEN→HOS, 2 segments. In minutes that is 12 + 4 = 16. However, ALM→MER→CEN→HOS is 3 segments but 4 + 5 + 4 = 13 minutes. BFS optimizes segments, not minutes: when weights matter, something else is needed (03-03). Keep this example in mind: it is the exact motivation for Dijkstra.

DFS: recursive and iterative

DFS explores "inwards": from a node it picks a neighbor, from that one another, and only when it can advance no further does it backtrack (literally the same explore/undo scheme from 02-03, applied to graphs).

The recursive version, the most natural one:

def dfs_recursive(graph, u, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(u)
    order.append(u)                      # moment of DISCOVERY
    for v in graph[u]:
        if v not in visited:
            dfs_recursive(graph, v, visited, order)
    return order

print(dfs_recursive(NETWORK, "ALM"))
# ['ALM', 'RIO', 'CEN', 'MER', 'UNI', 'EST', 'IND', 'HOS', 'PAR']

Follow the trail: from ALM it dives to RIO, from RIO to CEN, from CEN to MER, from MER to UNI, from UNI to EST, from EST to IND, from IND to HOS, from HOS to PAR. A single thread sinking to the bottom; the backtracking steps (for instance, from PAR all the way back to ALM) visit nothing new.

The iterative version with an explicit stack (LIFO), essential in large graphs where recursion would overflow (Python's default limit is around 1,000 nested calls):

def dfs_iterative(graph, source):
    visited, order = set(), []
    stack = [source]
    while stack:
        u = stack.pop()                  # LIFO: most recent one out first
        if u in visited:
            continue                     # it may have entered the stack several times
        visited.add(u)
        order.append(u)
        # reversed() to mimic the order of the recursive version
        for v in reversed(list(graph[u])):
            if v not in visited:
                stack.append(v)
    return order

Subtle differences worth internalizing:

The only structural difference from BFS is queue → stack. That change of structure turns the expanding wave into a plunge in depth. (A preview: in 03-03, swapping the stack for a heap will give Dijkstra. This whole family of algorithms is "the same template with a different agenda".)
In the iterative version, a node can sit in the stack several times; that is why visited is checked when popping, not when pushing.
DFS does not compute minimum distances: the discovery order depends on the order of the neighbors, and it can reach a node via a very long path.

BFS vs DFS comparison table

	BFS	DFS
Structure	Queue (FIFO)	Stack (LIFO) or recursion
Visit order	By levels (proximity)	In depth (one thread to the bottom)
Complexity	O(n + m)	O(n + m)
Worst-case memory	O(n) (wide frontier)	O(n) (deep path)
Shortest path without weights	Yes (in edges)	No
Cycle detection	Yes	Yes (the most convenient formulation in directed graphs)
Connected components	Yes	Yes
Topological sort	Kahn (BFS variant)	Reversed finish order
Typical uses in Rutalia	Distances in segments, reachable zones, service layers	Task dependencies, cycle detection, backtracking

Cycle detection

In undirected graphs: there is a cycle if during the search we find an already-visited neighbor that is not the parent of the current node (the parent doesn't count: the back-and-forth edge is not a cycle).

def has_cycle_undirected(graph):
    visited = set()
    def dfs(u, parent):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                if dfs(v, u):
                    return True
            elif v != parent:     # visited and not where we came from: cycle
                return True
        return False
    return any(u not in visited and dfs(u, None) for u in graph)

print(has_cycle_undirected(NETWORK))   # True (e.g. ALM-MER-CEN-ALM)

In directed graphs, "visited before" is not enough: we must distinguish whether the node is still on the current path. Three states are used: white (unvisited), gray (in progress, still on the recursion stack) and black (finished). Finding a gray neighbor betrays a directed cycle:

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}
    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:              # edge into the current path
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False
    return any(color[u] == WHITE and dfs(u) for u in graph)

This matters in Rutalia: if the warehouse task plan had a dependency cycle ("loading requires labeling, labeling requires loading"), no work order would be valid. Verifying that the graph is a DAG is the step that precedes sorting it.

Connected components: BFS versus the union-find of 01-04

Rutalia scenario: roadworks simultaneously close the EST–IND and HOS–IND segments. Is any zone left without service? It suffices to launch BFS from each not-yet-visited node; each launch discovers a complete component:

def components(graph):
    visited, comps = set(), []
    for start in graph:
        if start in visited:
            continue
        comp, queue = set(), deque([start])
        visited.add(start)
        while queue:
            u = queue.popleft()
            comp.add(u)
            for v in graph[u]:
                if v not in visited:
                    visited.add(v)
                    queue.append(v)
        comps.append(comp)
    return comps

trimmed = {u: {v: w for v, w in vs.items()
               if {u, v} not in [{"EST", "IND"}, {"HOS", "IND"}]}
           for u, vs in NETWORK.items()}
print(components(trimmed))
# [{'ALM','RIO','MER','EST','UNI','CEN','HOS','PAR'}, {'IND'}]

The Industrial Park ends up isolated — consistent with what we anticipated in 03-01: with degree 2, it was the most fragile zone.

And the union-find of 01-04? It solves the same thing: scan the edge list calling union(u, v), and two zones are in the same component if find returns the same representative. An honest comparison:

	BFS/DFS	Union-find
Cost	O(n + m) once	O(m · α(n)) ≈ linear
Static graph	Ideal	Correct but no advantage
Edges added live	Search must be relaunched	Ideal: O(α(n)) update per edge
Edges removed	Relaunch	Also needs rebuilding
Extras	Gives paths, distances, a tree	Component membership only

Practical rule: for a fixed snapshot, BFS; for a graph that grows edge by edge (exactly what Kruskal will do in 03-04), union-find.

Topological sort in DAGs: Kahn's algorithm

Rutalia's warehouse prepares each van with chained tasks: you cannot sort what hasn't been scanned, nor load what has no route assigned. We model each dependency as a directed edge "before → after":

graph LR
    receiving --> scanning
    scanning --> sorting
    scanning --> labeling
    sorting --> route_assignment
    labeling --> loading
    route_assignment --> loading
    loading --> departure

A topological sort is a list of the nodes in which every edge points forward: a valid execution order. It exists only if the graph is a DAG. Kahn's algorithm is BFS with one extra idea: only a task whose pending in-degree is 0 can start.

from collections import deque

def kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque(u for u in graph if in_degree[u] == 0)  # tasks ready now
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1        # u no longer blocks v
            if in_degree[v] == 0:
                queue.append(v)      # v becomes unblocked

    if len(order) < len(graph):      # some nodes stayed blocked on each other
        raise ValueError("There is a dependency cycle: no valid order exists")
    return order

TASKS = {
    "receiving": ["scanning"],
    "scanning": ["sorting", "labeling"],
    "sorting": ["route_assignment"],
    "labeling": ["loading"],
    "route_assignment": ["loading"],
    "loading": ["departure"],
    "departure": [],
}
print(kahn(TASKS))
# ['receiving', 'scanning', 'sorting', 'labeling',
#  'route_assignment', 'loading', 'departure']

Two valuable details:

The order is not unique (sorting and labeling are interchangeable: they are parallelizable tasks — useful information in itself for the warehouse manager).
Kahn detects cycles for free: if order does not contain every node at the end, the missing ones belong to (or depend on) a cycle. It is the "constructive" version of the gray/black cycle detector.

Applications in Rutalia: street closures and eccentricity

Let's recap the two promised operational questions, now with answers:

Which zones remain reachable if a street is closed? Remove the affected edges and relaunch BFS from ALM: nodes with no assigned distance are cut off. With the double closure around IND we saw the Industrial Park end up isolated; a single closure (for example only EST–IND) isolates nothing, because IND keeps its exit through HOS. This robustness analysis, systematized over giant graphs, will reappear in 06-02.
How many segments away is the farthest delivery point? max(dist.values()) after BFS from ALM: 2 segments (UNI, IND, PAR and HOS tie). That is the warehouse's eccentricity: useful for sizing logistic "hops", but misleading as a measure of time — HOS is 2 segments and 16 minutes away along that path, when a 13-minute one exists.

That crack — segments ≠ minutes — is exactly what opens the door to the next lesson.

Common Mistakes and Tips

Marking visited when dequeueing in BFS: it lets a node enter the queue many times and, worse, can assign it an incorrect distance. In BFS you mark when enqueueing; in iterative DFS, on the other hand, the convenient pattern is checking when popping. Don't mix the two patterns without thinking.
Using list.pop(0) as a queue: it shifts the whole list and turns BFS into O(n·m). Use collections.deque with popleft(), which is O(1).
Believing BFS gives the fastest path in minutes: it gives the minimum in edges. The ALM→HOS example (2 segments/16 min versus 3 segments/13 min) should vaccinate you forever.
Unbounded recursion in DFS: a path-shaped graph of 10,000 nodes blows Python's stack. For production, use the iterative version or sys.setrecursionlimit with great care.
Detecting cycles in directed graphs with a plain visited: two different paths to the same node are not a cycle. Directed graphs need the three colors (or Kahn).
Tip: when debugging a search, print the queue/stack at each iteration on a 5-node graph. The "mental video" of how the frontier advances is worth more than any definition.

Exercises

Zones by service layers. Rutalia wants to group zones into "rings" of proximity to the warehouse: ring 0 = ALM, ring 1 = one segment away, etc. Write rings(graph, source) returning a list of sets, one per BFS level, and apply it to the canonical network.
Critical closure? Write is_critical(graph, u, v) telling whether removing edge {u, v} disconnects the graph (hint: remove it and compare the number of components). Find all critical edges (bridges) of the canonical network by testing them one by one. Does the result square with the degrees you computed in 03-01?
Warehouse plan with a surprise. Add to the task DAG the dependency departure → receiving (a configuration error) and check that kahn raises the exception. Then write a variant kahn_parallel(graph) returning the tasks grouped into "waves" executable in parallel (everything unblocked at once forms one wave).

Solutions

Exercise 1:

def rings(graph, source):
    dist, _ = bfs(graph, source)
    levels = [set() for _ in range(max(dist.values()) + 1)]
    for node, d in dist.items():
        levels[d].add(node)
    return levels

print(rings(NETWORK, "ALM"))
# [{'ALM'}, {'RIO', 'MER', 'EST', 'CEN'}, {'PAR', 'UNI', 'IND', 'HOS'}]

We reuse bfs and simply regroup by distance: the rings are the layers of the expanding wave.

Exercise 2:

def without_edge(graph, u, v):
    return {a: {b: w for b, w in vs.items() if {a, b} != {u, v}}
            for a, vs in graph.items()}

def is_critical(graph, u, v):
    return len(components(without_edge(graph, u, v))) > len(components(graph))

critical = [(u, v) for u in NETWORK for v in NETWORK[u] if u < v and is_critical(NETWORK, u, v)]
print(critical)   # [] -> no single edge disconnects the network

The canonical network has no bridges: every zone has at least two exits, so no single closure isolates anything (consistent with the double-closure exercise around IND, which needed two edges). The u < v filter avoids examining each edge twice.

Exercise 3:

TASKS_BAD = dict(TASKS, departure=["receiving"])
try:
    kahn(TASKS_BAD)
except ValueError as e:
    print(e)   # There is a dependency cycle: no valid order exists

def kahn_parallel(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    ready = [u for u in graph if in_degree[u] == 0]
    waves = []
    while ready:
        waves.append(ready)
        upcoming = []
        for u in ready:
            for v in graph[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    upcoming.append(v)
        ready = upcoming
    return waves

print(kahn_parallel(TASKS))
# [['receiving'], ['scanning'], ['sorting', 'labeling'],
#  ['route_assignment'], ['loading'], ['departure']]

Instead of a node-by-node queue, we process complete generations: each wave contains tasks with no mutual dependencies, executable in parallel. Note that labeling must wait for route_assignment... no: it waits only for scanning; the one waiting for both branches is loading. The DAG makes the warehouse's real parallelism visible.

Conclusion

BFS and DFS are the same template with a different agenda: a queue produces a level-by-level wave giving minimum distances in edges and paths reconstructible with parent; a stack produces a plunge in depth, ideal for cycles, dependencies and backtracking. With them we have detected cycles (with three colors in directed graphs), computed connected components (and delimited when the union-find of 01-04 pays off), topologically sorted the warehouse tasks with Kahn, and answered Rutalia's street closures. But the lesson leaves a thorn behind: BFS swears the Hospital is "2 segments away" via a 16-minute avenue, when there is a 13-minute path. Counting edges is not enough when edges have weights. In 03-03 we will replace the queue with the heap we planted in 01-04 — time to cash in that seed — and obtain Dijkstra, the shortest-path algorithm par excellence, alongside Bellman-Ford and Floyd-Warshall.

Graph Search: BFS and DFS

Contents

BFS: level-by-level exploration with a queue

Distances in edges and path reconstruction with `parent`

DFS: recursive and iterative

BFS vs DFS comparison table

Cycle detection

Connected components: BFS versus the union-find of 01-04

Topological sort in DAGs: Kahn's algorithm

Applications in Rutalia: street closures and eccentricity

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Advanced Algorithms

Module 1: Introduction to Advanced Algorithms

Module 2: Optimization Algorithms

Module 3: Graph Algorithms

Module 4: Search and Sorting Algorithms

Module 5: Machine Learning Algorithms

Module 6: Case Studies and Applications

Module 7: Final Project

Graph Search: BFS and DFS

Contents

BFS: level-by-level exploration with a queue

Distances in edges and path reconstruction with parent

DFS: recursive and iterative

BFS vs DFS comparison table

Cycle detection

Connected components: BFS versus the union-find of 01-04

Topological sort in DAGs: Kahn's algorithm

Applications in Rutalia: street closures and eccentricity

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Advanced Algorithms

Module 1: Introduction to Advanced Algorithms

Module 2: Optimization Algorithms

Module 3: Graph Algorithms

Module 4: Search and Sorting Algorithms

Module 5: Machine Learning Algorithms

Module 6: Case Studies and Applications

Module 7: Final Project

Distances in edges and path reconstruction with `parent`