CONCEPT · 90 minutes
BFS, DFS, topological sort, and union-find — grounded in the cycle detection and graph reachability used in workflow-engine-rs. The most general structure in the path.
When I built workflow-engine-rs, the first thing I had to get right was cycle detection. A workflow is a DAG — a directed acyclic graph — and if a user accidentally created a circular dependency between tasks (A depends on B, B depends on A), the engine had to catch it at registration time, before any task started executing. Running a cycle-containing workflow would mean infinite execution: task A waits for B, B waits for A, nothing ever completes.
The solution was Kahn's algorithm: a topological sort that fails gracefully when a cycle exists. If the algorithm finishes processing fewer nodes than the graph contains, some nodes are in a cycle. That check runs at registration time and returns a validation error to the user before the engine touches a single task.
That is not a contrived academic example. It is the exact production use, and it is why graph algorithms belong in this foundations path.
Why graphs come last in this path: graphs are the most general structure here. Trees are directed acyclic graphs with a single root and no shared parents. Linked lists are linear graphs. BFS and DFS on graphs generalize the same algorithms you learned for trees, with one key addition: you need a visited set to prevent re-processing nodes in a cycle.
The standard representation: a dictionary from node to list of neighbors. Building and traversing takes O(V + E) — linear in vertices and edges.
Analogy: Graph traversal is like exploring a cave system with a map. BFS explores all tunnels at the current depth before going deeper — it finds the nearest chambers first. DFS picks one tunnel and follows it as far as possible before backtracking to try the next. In both cases, the visited set is your chalk mark on the wall: without it, you'd walk in circles forever.
graph LR
subgraph "5-node graph"
N0["0"] --- N1["1"]
N0 --- N2["2"]
N1 --- N3["3"]
N2 --- N4["4"]
end
subgraph "BFS from 0"
BF["Queue: [0]\nVisit 0 → enqueue 1,2\nQueue: [1,2]\nVisit 1 → enqueue 3\nVisit 2 → enqueue 4\nResult: [0,1,2,3,4]"]
endThe visited-set timing: in DFS, add a node to visited before processing its neighbors, not after. If you add it after, a cycle causes infinite recursion. In the clone-graph pattern, similarly, record the clone in your memo map before recursing into neighbors.
Graph algorithms work on grids too: treat each cell as a node, each adjacent cell as a neighbor.
For directed graphs, the standard visited boolean set is not enough — a node being visited in a different DFS path is not a cycle. You need to know whether the node is on the current DFS path.
Analogy: Think of a detective following a trail of leads. White means a lead hasn't been investigated yet. Gray means you're actively investigating it right now — it's open on your desk. Black means you closed it out completely. If following a new lead brings you back to something already on your desk (gray), you've found a loop — a circular dependency where A leads to B leads back to A.
The 3-color marking tracks this:
A back edge — reaching a gray node — means you've found a path back to a node still on the current path: a cycle.
This is the validation algorithm in workflow-engine-rs: when a workflow is registered, the task dependency graph is built and this DFS runs. If any cycle is found, registration fails with an error naming the involved tasks. No workflow with a circular dependency ever reaches the execution engine.
Topological sort orders nodes so every directed edge goes from earlier to later. Only possible on DAGs. I use Kahn's algorithm because cycle detection falls out naturally.
Why Kahn's detects cycles automatically: nodes in a cycle never reach in-degree 0. They wait forever for a prerequisite that also waits. The queue drains without them, len(order) < n, and you know a cycle exists without a separate detection pass.
Union-Find groups elements into connected components, answering "are these two nodes in the same group?" in nearly O(1) amortized time. It is the right tool for undirected cycle detection and for problems where you build the graph incrementally.
Analogy: Imagine a social network where everyone nominates a representative for their friend group. find(x) asks "who is your group's rep?" — you keep asking each person's nominee until you reach someone who nominated themselves. union(x, y) merges two groups by making one rep report to the other. Path compression is the shortcut: after you trace the chain to the root, you update everyone along the way to point directly to the root, so the next lookup skips the chain entirely.
Try these from memory:
visited set when tree BFS/DFS does not?union(A, B) returns False. What does this mean for the undirected graph edge A—B?Reflective prompt: the SDLC harness that orchestrates the agents writing these modules uses topological sort to determine which tasks can run in parallel. Tasks with no dependencies run first; dependent tasks wait. A circular dependency between two tasks would deadlock the harness — both would wait forever. The same algorithm that validates your build system is running underneath any agentic workflow orchestrator. Understanding it makes you a better systems engineer, regardless of whether you ever write another graph problem.
Problem: Course Schedule II
There are numCourses courses (labeled 0 to numCourses-1). prerequisites[i] = [a, b] means course b must be taken before course a. Return a valid order to take all courses, or [] if impossible (cycle).
Hint 1: When a course is dequeued, decrement the in-degree of every course that depends on it. If that course's in-degree reaches 0, it is now ready — enqueue it.
Hint 2: Cycle detection is implicit. len(order) == numCourses means all courses were scheduled (DAG). len(order) < numCourses means some courses are in a cycle (return []).
Hint 3: The output order is a valid topological ordering of the courses — you could follow it literally to take every course in a valid sequence.
Why this problem matters beyond the exercise: this is exactly what runs inside workflow-engine-rs at registration time, inside package managers when installing dependencies, and inside build systems like Bazel or Make when computing build order. Understanding the algorithm means you understand the validation layer of any orchestration system. That understanding is portable to every language and every framework — the algorithm does not change.
Application-level questions on graph traversal, cycle detection, and topological sort
1. An adjacency list graph with V vertices and E edges: what is the time complexity of visiting all edges in a DFS/BFS traversal?
Correct Answer: C
You visit each vertex once (O(V)) and process each edge once (O(E)), giving O(V + E) total. This is why adjacency lists are preferred over adjacency matrices for sparse graphs — a matrix would be O(V^2) even if E is small.
2. In the 3-color DFS cycle detection for directed graphs, what do the three colors mean?
Correct Answer: A
White = not started. Gray = DFS is currently exploring this node (it's on the recursion stack). Black = fully processed (all descendants explored). A back edge — from a gray node to another gray node — indicates a cycle, because you've found a path back to a node already on the current DFS path.
3. Kahn's topological sort starts with nodes whose in-degree is 0. When is a cycle detected?
Correct Answer: B
In a DAG, every node eventually reaches in-degree 0 and is processed. In a graph with a cycle, the nodes in the cycle never reach in-degree 0 (they depend on each other). So Kahn's finishes with fewer processed nodes than V — if `len(order) < V`, a cycle exists.
4. Union-find with path compression: what does path compression do to the 'find' operation?
Correct Answer: B
Path compression, during a find, makes every node on the path to the root point directly to the root. Future finds on those nodes are O(1). Combined with union-by-rank, the amortized cost of find is essentially O(1) — technically O(alpha(n)) where alpha is the inverse Ackermann function, which is <= 4 for any practical n.
5. Which real-world problem is topological sort directly solving?
Correct Answer: B
Topological sort gives a linear ordering of nodes such that every directed edge goes from earlier to later. This is exactly what a build system, package manager, or task scheduler needs: execute A before B if B depends on A. If a cycle exists (circular dependency), no valid topological order exists — which is the 'cycle detected' error you see in build tools.
Nice work. Here's what's next.
Back to this pathOr book the diagnostic call