Cycles, Topological Sort, Bipartite Check

Build systems, course plans and spreadsheet formulas hide the same question: in what order can we do things that depend on each other, and is there a loop that makes it impossible? DFS with three colours answers both in linear time.

intermediate⏱ 14 min read

←Builds on

6Depth-First Search (DFS)Cycle detection and topological order are read off DFS entry and exit times.6Breadth-First Search (BFS)The bipartite check colours vertices layer by layer, following BFS's waves.

Leads to→

10DP Fundamentals: Memo & TableDP states form a DAG, and a table must be filled in topological order.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Cycles in directed graphs

In a directed graph, “I reached a visited vertex” is not enough to claim a cycle: that vertex may have been finished on another branch. You need all three colours. During DFS at u, look at each edge u → w:

w white: a tree edge, recurse;
w gray: w is still on the recursion stack, an ancestor of u, so the path w → … → u plus the edge u → w is a cycle;
w black: w and everything below it is finished; no cycle through here.

In the course graph the DFS path 1 → 2 → 4 → 5 is gray when we meet the new edge 5 → 1 (AI → Intro). Vertex 1 is gray, so we found a cycle, and no study plan can exist. To print the cycle, keep parents and walk back from u to w.

In an undirected graph the rule is simpler: any visited neighbour other than your parent closes a cycle.

02Topological sort with DFS

A DAG (directed acyclic graph) can be laid out in a line so that every edge points forward: a topological order. Every prerequisite comes before the course that needs it.

DFS gives it almost for free. When a vertex finishes (turns black), everything it points to has already finished. So list the vertices by decreasing tout: append each vertex to a list when it finishes, then reverse the list. On the course DAG, starting from Intro: AI finishes first, then Algo, DB, DataStr, Discrete, and Intro last. Reversed: Intro, Discrete, DataStr, DB, Algo, AI.

Run the outer loop over all vertices, not just one start, and keep the gray check: if a cycle shows up, report that no order exists. Time O(V + E). Topological orders are usually not unique; any order with all arrows pointing forward is valid.

The course DAG laid out in topological order: every arrow points right.

03Kahn’s algorithm: the queue way

A second classic method uses a queue instead of recursion. Count the in-degree of every vertex, how many arrows point into it. Vertices with in-degree 0 have no prerequisites: put them in a queue. Repeatedly pop a vertex, append it to the order, and “remove” its outgoing edges by decrementing the in-degree of each target; whenever one drops to 0, push it.

If all V vertices are output, you have a topological order. If the queue empties early, the remaining vertices all sit on a cycle or behind one, so Kahn’s algorithm detects cycles too. Time O(V + E).

Kahn is handy when you want the order level by level (which tasks can run in parallel in round 1, round 2, …) or the lexicographically smallest order (use a min-heap instead of the queue). The DFS version is shorter to write.

04Is the graph bipartite?

A graph is bipartite if its vertices can be split into two groups so that every edge runs between the groups: students and courses, workers and jobs, or a map coloured with two colours so that neighbours always differ.

Test it by trying to 2-colour the graph with BFS or DFS: give the start colour 0, every neighbour the opposite colour, and so on. If you ever meet an edge whose ends already have the same colour, the graph is not bipartite. Start again from every uncoloured vertex to cover all components. O(V + E).

Theorem: a graph is bipartite exactly when it has no odd cycle. Around a cycle the colours must alternate, which works only for an even length. In the triangle on the right, 2 and 3 are forced to share a colour while an edge joins them; the 6-cycle on the left is fine.

Cost at a glance

Cycle detection (3 colours)O(V + E)

Topological sort (DFS or Kahn)O(V + E)

Bipartite checkO(V + E)

Remember

In a directed graph, an edge to a gray vertex, one still on the DFS stack, proves a cycle.
Reversed DFS finishing order is a topological order of a DAG; Kahn’s in-degree queue gives one too and detects cycles.
A graph is bipartite iff it can be 2-coloured, iff it has no odd cycle; BFS or DFS checks it in O(V + E).

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the order strip: a course is added at the front only when it finishes. Then the extra edge 5 → 1 turns the DAG into a cycle.

Interactive visualizerfocus here, then space ← →

Course DAG (directed)

1 Intro → 2 DataStr, 3 Discrete · 2 → 4 Algo, 6 DB · 3 → 4 · 4 → 5 AI

Topological order

∅

A directed acyclic graph (DAG) of course prerequisites. Topological sort lists courses so every prerequisite comes before the course needing it.

Pseudocode

 1 topological sort of a DAG: 2   dfs(u): for each edge u→w, recurse on unvisited w 3   on finishing u, prepend u to the order 4 reverse finish order = valid dependency order 5 if dfs meets a gray vertex → cycle → no order exists

1 / 1

Check

Three questions. Pick an answer to see why.

DFS finishes the vertices of a DAG in the order C, E, B, D, A. Which is a topological order?

Kahn’s algorithm outputs 4 vertices of a 6-vertex directed graph and then the queue is empty. What does that mean?

Which of these graphs is NOT bipartite?

Practice

Real problems to lock it in, easiest first.

LeetCodeCourse Schedule intermediate↗LeetCodeIs Graph Bipartite? intermediate↗CSESBuilding Teams intermediate↗CSESCourse Schedule intermediate↗CSESRound Trip intermediate↗