The Project | About Us | Contribute | Donations | License

HOME

This is the lesson where the course collects on all its debts. In module 5 we promised that the "have I seen this already?" pattern with a set would become BFS's visited; in module 6 we said that level-order traversal with a deque "is a BFS that will leap to graphs"; and since module 3 we've known that every recursion hides a stack. Here the three pieces converge: BFS (breadth-first search) and DFS (depth-first search), the two fundamental graph traversals. With them we'll answer real TaskFlow questions: which tasks get unblocked when one finishes, whether the project has dependency cycles, and in what order to execute the tasks. We work on the Graph class and the dependencies graph from the previous lesson.

Why visited is now indispensable
BFS: breadth-first search with deque
BFS trace on the dependency graph
DFS: depth-first search, recursive and iterative
DFS trace and BFS/DFS comparison
Application 1: what does finishing a task unblock? (reachability)
Application 2: cycle detection with white/gray/black states
Application 3: topological order (Kahn's algorithm)
Connected components

Why `visited` is now indispensable

In a tree's level-order traversal (module 6) we carried no visited set. We didn't need one: in a tree every node has a single parent, so it can only be reached by one path and it's impossible to enqueue it twice. Graphs break that guarantee twice over:

Multiple parents: deploy_api is reachable from migrate_db and from configure_server. Without a guard, we'd process it twice (and everything behind it, four times; exponential growth).
Cycles: in A → B → C → A, a naive traversal never terminates.

The solution is module 5's pattern: a set named visited with average O(1) membership and insertion. Golden rule: mark when enqueueing/pushing, not when dequeuing — if you wait to mark until you process the vertex, it can sneak into the queue twice in the meantime.

BFS: breadth-first search with `deque`

BFS explores the graph in layers of distance: first the source (distance 0), then its neighbors (distance 1), then their neighbors (distance 2)... It is literally module 6's level-order traversal, with a deque as the queue (append on the right, popleft on the left, both O(1), module 4), plus the visited set:

from collections import deque

def bfs(graph, source):
    """Traverses the graph from source in layers. Returns the visit order."""
    visited = {source}            # marked ALREADY, before entering the queue
    queue = deque([source])
    order = []
    while queue:
        current = queue.popleft() # FIFO: oldest out first -> layer by layer
        order.append(current)
        for neighbor in graph.neighbors(current):
            if neighbor not in visited:   # module 5's "have I seen this?"
                visited.add(neighbor)     # mark when enqueueing
                queue.append(neighbor)
    return order

Each vertex enters the queue at most once and each edge is examined once: cost O(n + a) in time and O(n) in space. Compare it with the tree code from module 6: it's almost identical; we've only added three lines of visited. That's the promised continuity.

BFS's star property: because it advances in layers, the first time it reaches a vertex, it does so along a path with the minimum number of edges. On unweighted graphs, BFS is the shortest-path algorithm (once weights appear it won't suffice: lesson 07-04).

BFS trace on the dependency graph

Let's run bfs(dependencies, "design_schema") step by step:

graph LR
    A[design_schema] --> B[migrate_db]
    B --> C[deploy_api]
    S[configure_server] --> C
    C --> D[integration_tests]
    U[design_ui] --> I[implement_ui]
    I --> D
    D --> L[launch]

Step	Leaves the queue	New neighbors entering	Queue after the step	Visited
1	design_schema	migrate_db	[migrate_db]	{d_s, mig}
2	migrate_db	deploy_api	[deploy_api]	+ api
3	deploy_api	integration_tests	[integration_tests]	+ tst
4	integration_tests	launch	[launch]	+ lau
5	launch	—	[]	—

Result: ['design_schema', 'migrate_db', 'deploy_api', 'integration_tests', 'launch']. Two observations:

BFS only visits what is reachable by following the arrows: neither configure_server, nor design_ui, nor implement_ui shows up, because no arrow leads from design_schema to them. In a directed graph, "reachable" depends on the source.
The layers are the distances: migrate_db at 1 edge, deploy_api at 2, and so on.

DFS: depth-first search, recursive and iterative

DFS makes the opposite call: instead of exhausting the current layer, it dives down one path to the bottom and only backtracks when it can't continue. Recursive version, where the "stack" is module 3's call stack:

def dfs_recursive(graph, source, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(source)
    order.append(source)
    for neighbor in graph.neighbors(source):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)  # go one level down
    return order

And the iterative version, applying module 3's recursion ↔ explicit stack equivalence (useful when the graph is deep and Python's call stack, capped at ~1000 levels, runs out):

def dfs_iterative(graph, source):
    visited = set()
    stack = [source]              # a list as a stack: append/pop at the end
    order = []
    while stack:
        current = stack.pop()     # LIFO: most RECENT out first -> depth
        if current in visited:    # it may have entered twice before leaving
            continue
        visited.add(current)
        order.append(current)
        for neighbor in graph.neighbors(current):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

Compare dfs_iterative with bfs: they are the same algorithm with a different supporting structure. Queue (FIFO) → breadth; stack (LIFO) → depth. It's the stack↔DFS / queue↔BFS symmetry announced in module 6, now in real code.

DFS trace and BFS/DFS comparison

dfs_recursive(dependencies, "design_ui"): it visits design_ui, descends to implement_ui, descends to integration_tests, descends to launch; with no new neighbors, it unwinds the calls back to the source. Result: ['design_ui', 'implement_ui', 'integration_tests', 'launch'] — a nosedive down one path, versus BFS's layer-by-layer advance.

Criterion	BFS	DFS
Supporting structure	Queue (`deque`, module 4)	Stack (calls or `list`, module 3)
Exploration order	By layers of distance	One path to the bottom, then backtrack
Finds	The path with the fewest edges	Exhaustive exploration; paths, not necessarily short
Worst-case memory	`O(n)` (one wide layer)	`O(n)` (one long path)
Time cost	`O(n + a)`	`O(n + a)`
Typical uses	Distances, "within N steps of", levels	Cycles, orderings, backtracking

Application 1: what does finishing a task unblock? (reachability)

TaskFlow question: "if I finish migrate_db, which tasks move closer to being unblocked?" With our convention (the arrow points at what gets unblocked), they are exactly the vertices reachable from it — BFS minus the source:

def affected_tasks(graph, task_id):
    """Tasks that depend, directly or transitively, on task_id."""
    return bfs(graph, task_id)[1:]      # everything reachable, minus itself

print(affected_tasks(dependencies, "migrate_db"))
# ['deploy_api', 'integration_tests', 'launch']

Delaying migrate_db potentially delays those three tasks: we've just implemented a project manager's impact analysis in five lines.

Application 2: cycle detection with white/gray/black states

In module 2 we detected cycles in linked lists with Floyd's algorithm (two pointers at different speeds). That technique worked because a list has only one possible path; in a graph with branches we need a different idea, but the problem is the same: can I come back to a place where I already am? The classic technique uses DFS with three states per vertex:

White: not visited yet.
Gray: in progress — it's on the recursion's current path (on the call stack).
Black: finished — it and all its descendants, fully explored.

The key: if DFS finds an edge to a gray vertex, it has found an edge back into the current path: a cycle. Reaching a black one is not a cycle, just paths crossing (multiple parents).

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph.vertices()}

    def visit(v):
        color[v] = GRAY
        for neighbor in graph.neighbors(v):
            if color[neighbor] == GRAY:    # edge back into the current path
                return True
            if color[neighbor] == WHITE and visit(neighbor):
                return True
        color[v] = BLACK                   # v closed: nothing below it cycles
        return False

    # the graph may not be connected: try from every white vertex
    return any(color[v] == WHITE and visit(v) for v in graph.vertices())

print(has_cycle(dependencies))    # False: our project is a DAG

# Let's break it on purpose: "design_ui depends on integration_tests"
dependencies.add_edge("integration_tests", "design_ui")
print(has_cycle(dependencies))    # True
dependencies.remove_edge("integration_tests", "design_ui")  # ex. 2 of 07-02

This is exactly what TaskFlow must run before accepting a new dependency: if adding it makes has_cycle return True, it gets rejected and the user is warned. In the 07-07 exercises we'll go further: not just detect the cycle, but list it to show the user.

Application 3: topological order (Kahn's algorithm)

The project's big question: in what order do I execute the tasks so that none starts before its dependencies? That order is called a topological order and it only exists in DAGs. Kahn's algorithm builds it with two pieces we already have: 07-02's in_degrees() and a queue:

Compute each vertex's in-degree.
Put the degree-0 ones in the queue (runnable right now).
Take one out, append it to the order, and "finish" it: subtract 1 from each neighbor's degree. If any hits 0, into the queue.
Repeat until the queue empties.

def topological_order(graph):
    degrees = graph.in_degrees()
    queue = deque(v for v, d in degrees.items() if d == 0)
    order = []
    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph.neighbors(current):
            degrees[neighbor] -= 1     # one dependency fewer
            if degrees[neighbor] == 0: # all satisfied: runnable
                queue.append(neighbor)
    if len(order) < len(degrees):      # vertices with degree > 0 remained
        raise ValueError("There is a dependency cycle: no valid order exists")
    return order

print(topological_order(dependencies))
# ['design_schema', 'configure_server', 'design_ui', 'migrate_db',
#  'implement_ui', 'deploy_api', 'integration_tests', 'launch']

Important details:

There's no visited here: the degree counter plays its role — a vertex enters the queue only when its degree hits exactly 0, and that happens once.
The final check throws in a second cycle detector for free: if there's a cycle, its vertices never drop to degree 0 and the order comes out incomplete. Kahn detects cycles "on the house", no colors needed.
The order is not unique (the three initial degree-0 vertices could come out in any order). In 07-07 we'll break ties by priority by replacing the deque with module 4's heapq.
Cost: O(n + a), like everything today.

Connected components

Last tool: detecting the graph's "islands". For this we ignore the direction of the arrows (two tasks are related if they share dependencies in either direction) and launch BFS from every not-yet-visited vertex; each launch discovers one whole component:

def connected_components(graph):
    # undirected version of the graph: every edge, in both directions
    und = Graph(directed=False)
    for v in graph.vertices():
        und.add_vertex(v)
        for target in graph.neighbors(v):
            und.add_edge(v, target)

    visited, components = set(), []
    for v in und.vertices():
        if v not in visited:
            comp = bfs(und, v)             # discovers v's entire island
            visited.update(comp)
            components.append(comp)
    return components

dependencies.add_edge("write_blog", "publish_blog")  # separate mini-project
print(len(connected_components(dependencies)))   # 2: the main project and the blog

In TaskFlow, each component is an independent subproject: it can be planned, assigned, and executed without looking at the others. We'll come back to this in the exercises (07-07) with "task islands".

Common Mistakes and Tips

Marking as visited when dequeuing instead of when enqueueing. The algorithm still terminates, but the same vertex can enter the queue several times and the cost blows up. In BFS, mark on enqueue; in iterative DFS, the continue after the pop covers the equivalent case.
Using a list as the BFS queue (pop(0)): that's O(n) per extraction, as we hammered home in module 4. deque.popleft() is O(1).
Detecting cycles by checking "neighbor already visited" with a single set. In directed graphs, reaching a black (finished) vertex by another path is not a cycle — it's a perfectly legal dependency diamond. Without the gray state, you'll get false positives.
Forgetting the graph may not be connected. has_cycle and connected_components iterate over all vertices; if you only launch from one, the islands go unexplored.
Recursive DFS on huge graphs: Python's call stack runs out (~1000 levels, module 3). For deep graphs, the iterative version.
Tip: when torn between BFS and DFS, ask yourself what you're looking for. Distances or "the nearest"? BFS. Cycles, orderings, exploring everything regardless of order? DFS is usually more natural.

Exercises

Exercise 1: BFS with distances

Modify bfs so it returns a dict mapping vertex → distance (minimum number of edges from the source). Use it to answer: how many "hops" from design_schema is launch?

Exercise 2: what does this task depend on?

affected_tasks looks forward. Write prerequisites(graph, task_id) returning every task that task_id depends on, directly or transitively. Hint: either reverse the graph, or search from every vertex.

Exercise 3: Kahn trace

Without running any code, trace topological_order on the dependency graph in a table (queue, extracted, degrees that change) and verify it matches the output shown in the lesson.

Solutions

Solution 1:

def bfs_distances(graph, source):
    distances = {source: 0}           # doubles as the visited set
    queue = deque([source])
    while queue:
        current = queue.popleft()
        for neighbor in graph.neighbors(current):
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

print(bfs_distances(dependencies, "design_schema")["launch"])  # 4

The distances dict replaces the visited set: being in it already means "seen". launch is 4 hops away, as in the trace.

Solution 2:

def reverse(graph):
    rev = Graph(directed=True)
    for v in graph.vertices():
        rev.add_vertex(v)
        for target, weight in graph.neighbors(v).items():
            rev.add_edge(target, v, weight)   # the arrow, flipped
    return rev

def prerequisites(graph, task_id):
    return bfs(reverse(graph), task_id)[1:]

print(prerequisites(dependencies, "deploy_api"))
# ['migrate_db', 'configure_server', 'design_schema']

Reversing the graph costs O(n + a) and turns "who depends on me?" into "who do I depend on?": the same BFS answers both questions depending on which way the arrows point.

Solution 3:

Step	Queue before	Extracted	Degrees going down	New degree-0
1	[d_schema, c_server, d_ui]	design_schema	migrate_db: 1→0	migrate_db
2	[c_server, d_ui, migrate_db]	configure_server	deploy_api: 2→1	—
3	[d_ui, migrate_db]	design_ui	implement_ui: 1→0	implement_ui
4	[migrate_db, implement_ui]	migrate_db	deploy_api: 1→0	deploy_api
5	[implement_ui, deploy_api]	implement_ui	tests: 2→1	—
6	[deploy_api]	deploy_api	tests: 1→0	integration_tests
7	[integration_tests]	integration_tests	launch: 1→0	launch
8	[launch]	launch	—	—

Final order: the lesson's. Notice how no task comes out before all its dependencies have come out: that's the topological order's guarantee.

Conclusion

BFS and DFS are the two exploration engines for graphs: same machinery, different supporting structure (queue → layers and minimum edge-count distances; stack → depth, cycles, and orderings), both O(n + a) thanks to the visited set module 5 left ready for us. On top of them we've built the three operations TaskFlow needed: impact analysis (reachability), rejection of circular dependencies (white/gray/black, Floyd's graph sibling), and the project's execution order (Kahn). But BFS measures paths in number of edges, and in real life edges don't all cost the same: passing through an 8-hour task is not like passing through a 1-hour one. When edges carry weights, something better is needed — and that something, Dijkstra, reuses module 4's heapq priority queue. That's the next lesson.

Graph Search Algorithms

Contents

Why `visited` is now indispensable

BFS: breadth-first search with `deque`

BFS trace on the dependency graph

DFS: depth-first search, recursive and iterative

DFS trace and BFS/DFS comparison

Application 1: what does finishing a task unblock? (reachability)

Application 2: cycle detection with white/gray/black states

Application 3: topological order (Kahn's algorithm)

Connected components

Common Mistakes and Tips

Exercises

Exercise 1: BFS with distances

Exercise 2: what does this task depend on?

Exercise 3: Kahn trace

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Graph Search Algorithms

Contents

Why visited is now indispensable

BFS: breadth-first search with deque

BFS trace on the dependency graph

DFS: depth-first search, recursive and iterative

DFS trace and BFS/DFS comparison

Application 1: what does finishing a task unblock? (reachability)

Application 2: cycle detection with white/gray/black states

Application 3: topological order (Kahn's algorithm)

Connected components

Common Mistakes and Tips

Exercises

Exercise 1: BFS with distances

Exercise 2: what does this task depend on?

Exercise 3: Kahn trace

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Why `visited` is now indispensable

BFS: breadth-first search with `deque`