Data Structures & Algorithms (DSA) Module 11 – Graphs: modelling, traversal and connectivity
Cycle detection and bipartite graphs
Detect cycles in undirected and directed graphs with DFS colours, test whether a graph is bipartite by BFS colouring, and return the cycle that proves it.
What you will learn
- Detect cycles in undirected and directed graphs
- Check bipartiteness with BFS colouring
- Report a certificate (a cycle or an odd cycle) with the answer
Before you start
What you’ll learn · Before you start
What you will learn
- Detect cycles in undirected and directed graphs
- Check bipartiteness with BFS colouring
- Report a certificate (a cycle or an odd cycle) with the answer
Before you start
On this page
Cycle detection asks whether a graph contains a cycle, and a good answer returns the cycle itself, so that anyone can check it. In an undirected graph, a depth-first search that reaches an already visited vertex along any edge other than the one it arrived by has closed a cycle. In a directed graph that is not enough, and DFS colours every vertex white (not reached), grey (open, on the current path) or black (finished): an arc into a grey vertex closes a cycle, while an arc into a black one does not. Bipartite graphs are the graphs whose vertices split into two sides with every edge between the sides, and a graph is bipartite exactly when it has no cycle of odd length. A BFS that gives each vertex the opposite side to the vertex it came from either finds such a split or meets an edge whose ends got the same side, which yields an odd cycle as proof. All three checks run in O(V + E).
Cycle detection in undirected graphs
Eight routers are joined by cables. A search that remembers which cable it arrived by can tell a loop from the way back: reaching a visited router by any other cable closes a loop, and the parent pointers from the current router up to the visited one, plus that cable, are the loop.
# Cycle detection in an undirected graph: eight routers joined by cables, given as a numbered list. A DFS remembers the
# cable it arrived by; reaching an already visited router by any other cable closes a loop, and the parent pointers
# give the loop itself. Tracking the cable's number, not just the router it came from, also catches two cables between
# the same pair of routers.
cables = [("R1", "R2"), ("R2", "R3"), ("R3", "R4"), ("R4", "R5"), ("R2", "R6"), ("R6", "R7"), ("R7", "R3"), ("R5", "R8")]
def find_loop(cables):
adj = {}
for i, (a, b) in enumerate(cables):
adj.setdefault(a, []).append((b, i))
adj.setdefault(b, []).append((a, i))
parent = {} # router -> (router it was reached from, cable number)
for start in adj:
if start in parent:
continue
parent[start] = (None, None)
stack = [(start, iter(adj[start]))]
while stack:
u, it = stack[-1]
for v, cable in it:
if cable == parent[u][1]:
continue # the cable we arrived by
if v in parent: # visited before: this cable closes a loop
loop = [u]
while loop[-1] != v:
loop.append(parent[loop[-1]][0])
return loop + [u]
parent[v] = (u, cable)
stack.append((v, iter(adj[v])))
break
else:
stack.pop()
return []
print("loop:", " - ".join(find_loop(cables)))
print("without the R7-R3 cable:", find_loop([c for c in cables if c != ("R7", "R3")]) or "no loop: the network is a tree")
twice = [("R1", "R2"), ("R2", "R3"), ("R2", "R3")]
print("two cables between R2 and R3:", " - ".join(find_loop(twice)))Output
loop: R6 - R7 - R3 - R2 - R6 without the R7-R3 cable: no loop: the network is a tree two cables between R2 and R3: R3 - R2 - R3
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 undirected.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Two details make this rule right. It must skip the arrival cable by its number, not every cable to the parent router, or two cables between the same pair of routers, a cycle of length 2, are skipped together. And a loop on one router, a cable from a router to itself, is a cycle of length 1, which the same rule reports.
Cycle detection in directed graphs: three colours
Cycle detection in a directed graph needs more than a visited mark. If module A imports B and C, and B also imports C, then C is reached twice, yet there is no cycle. The three colours fix that. A vertex turns grey when the search reaches it and black when everything reachable from it has been explored, so the grey vertices are exactly the path from the start to the current vertex. An arc into a grey vertex points back up that path and closes a cycle; an arc into a black vertex points at finished work.
# Cycle detection in a directed graph: the import graph of a made-up program, where "a imports b" is an arc a -> b.
# DFS colours each module white (not reached), grey (open: on the current path) or black (finished). An arc to a grey
# module is a back edge, and the grey path from that module down to the current one, plus the arc, is the cycle.
imports = {
"app": ["api", "ui"],
"ui": ["api", "theme"],
"api": ["auth", "db"],
"auth": ["session"],
"session": ["user"],
"user": ["auth", "db"],
"db": ["config"],
"config": [],
"theme": [],
"logging": [],
}
WHITE, GREY, BLACK = 0, 1, 2
def find_cycle(graph):
colour = {m: WHITE for m in graph}
parent = {}
for start in graph:
if colour[start] != WHITE:
continue
colour[start] = GREY
stack = [(start, iter(graph[start]))]
while stack:
u, it = stack[-1]
for v in it:
if colour[v] == GREY: # back edge u -> v: walk the grey path from u up to v
cycle = [u]
while cycle[-1] != v:
cycle.append(parent[cycle[-1]])
return cycle[::-1] + [v]
if colour[v] == WHITE:
colour[v] = GREY
parent[v] = u
stack.append((v, iter(graph[v])))
break
else:
colour[u] = BLACK
stack.pop()
return []
print("cycle:", " -> ".join(find_cycle(imports)))
imports["user"] = ["db"] # user stops importing auth
print("after user stops importing auth:", find_cycle(imports) or "no cycle")
imports["config"] = ["app"] # a new import closes a longer cycle
print("after config imports app:", " -> ".join(find_cycle(imports)))Output
cycle: auth -> session -> user -> auth after user stops importing auth: no cycle after config imports app: app -> api -> auth -> session -> user -> db -> config -> app
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 modules.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The first cycle the search reports is auth, session, user, auth. Removing one import breaks it, and a new import from config to app closes a longer cycle of seven modules, which the same search returns in full.
Bipartite graphs by BFS colouring
Nine exam papers must go into a morning and an afternoon session so that no two papers that share a student sit in the same session. Papers are vertices and shared students are edges, so the question is whether the graph is bipartite. BFS from each unreached paper puts every newly reached paper in the opposite session to the one it was reached from.
# Bipartite graphs by BFS colouring: can nine exam papers be split into a morning and an afternoon session so that no
# two papers that share a student are in the same session? Papers are vertices and shared students are edges. BFS gives
# each paper the opposite session to the paper it was reached from; an edge whose ends got the same session proves that
# no split exists, and the two BFS tree paths from its ends to their common ancestor, plus the edge, form an odd cycle.
from collections import deque
papers = ["MA", "PH", "CH", "CS", "BI", "EC", "HI", "EN", "GE"]
clashes = [("MA", "PH"), ("MA", "CH"), ("CS", "PH"), ("CS", "CH"), ("BI", "EC"), ("EC", "HI"), ("HI", "EN"), ("EN", "GE")]
def two_sessions(papers, clashes):
adj = {p: [] for p in papers}
for a, b in clashes:
adj[a].append(b)
adj[b].append(a)
side, parent, level = {}, {}, {}
for start in papers:
if start in side:
continue
side[start], parent[start], level[start] = 0, None, 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in side:
side[v], parent[v], level[v] = 1 - side[u], u, level[u] + 1
queue.append(v)
elif side[v] == side[u]: # both ends in one session: build the odd cycle
a, b = u, v
left, right = [a], [b]
while a != b: # climb from the deeper end until the two paths meet
if level[a] >= level[b]:
a = parent[a]
left.append(a)
else:
b = parent[b]
right.append(b)
return None, left + right[-2::-1] + [u]
return side, None
side, cycle = two_sessions(papers, clashes)
print("morning: ", " ".join(p for p in papers if side[p] == 0))
print("afternoon:", " ".join(p for p in papers if side[p] == 1))
assert all(side[a] != side[b] for a, b in clashes)
print(f"all {len(clashes)} clashes are split between the sessions")
print()
clashes.append(("GE", "BI"))
side, cycle = two_sessions(papers, clashes)
print("after a student takes both GE and BI: no split exists")
print(f"odd cycle of {len(cycle) - 1} clashes:", " - ".join(cycle))Output
morning: MA CS BI HI GE afternoon: PH CH EC EN all 8 clashes are split between the sessions after a student takes both GE and BI: no split exists odd cycle of 5 clashes: HI - EC - BI - GE - EN - HI
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 sessions.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Two sessions from BFS colouring, and the clash that makes a split impossible
Text description of the diagram
The morning session holds MA, CS, BI, HI and GE; the afternoon session holds PH, CH, EC and EN. A line joins two papers that share a student.
- Every one of the eight original clashes joins a morning paper to an afternoon paper: MA with PH and CH, CS with PH and CH, BI with EC, HI with EC and EN, and GE with EN.
- The new clash, drawn dashed, joins GE and BI, which are both in the morning.
With the new clash the papers HI, EC, BI, GE and EN form a cycle of five clashes. An odd cycle cannot alternate between two sessions, so no split of all nine papers into two sessions exists.
With eight clashes the colouring works. One more student taking both GE and BI puts two morning papers in conflict, and the program returns the odd cycle HI, EC, BI, GE, EN: five clashes in a ring, which no two-way split can satisfy, because the sessions would have to alternate around an odd number of edges. Trees, even cycles and grids are bipartite graphs; triangles and every graph containing one are not.
GATE CS
The GATE syllabus lists “Graphs: connectivity, matching, colouring” under Discrete Mathematics. A graph can be coloured with two colours exactly when it is bipartite, and matching problems usually start from a bipartite graph, such as students and the projects they may take.
Exercise and self-check
Return a directed cycle, or an empty list when there is none.
Exercise · Medium · Python, JavaScript
Return a directed cycle, or an empty list
A directed graph has n vertices, numbered 0 to n - 1, and a list of arcs (u, v), each running from u to v (JavaScript: two-element arrays). Write find_cycle(n, arcs) (JavaScript: findCycle(n, arcs)), which returns one directed cycle as a list of distinct vertices [c0, c1, ..., ck] such that every ci has an arc to the next one and ck has an arc back to c0, or an empty list when the graph has no directed cycle.
Any cycle is accepted: the tests check the one you return arc by arc. A loop (v, v) is a cycle [v] of its own. The tests include graphs without cycles, two-vertex cycles, cycles reachable only from a vertex late in the numbering, random graphs checked against a slow method, and a chain of 100,000 vertices whose only cycle is closed by its last arc, so a recursive search would go 100,000 calls deep.
Python · Starter code · cycle.py
def find_cycle(n, arcs):
"""One directed cycle [c0, ..., ck] (ck has an arc back to c0), or [] if the graph has none."""
raise NotImplementedError("write find_cycle")The sample tests · test_cycle.py
import random
from cycle import find_cycle
def check_cycle(arcs, cycle):
"""distinct vertices, an arc from each to the next, and one from the last back to the first"""
have = set(arcs)
assert cycle and len(set(cycle)) == len(cycle), cycle
for i, u in enumerate(cycle):
assert (u, cycle[(i + 1) % len(cycle)]) in have, (u, cycle[(i + 1) % len(cycle)])
def slow_has_cycle(n, arcs):
"""some arc u -> v with u reachable from v"""
adj = [[] for _ in range(n)]
for u, v in arcs:
adj[u].append(v)
def reach(s):
seen, stack = {s}, [s]
while stack:
for w in adj[stack.pop()]:
if w not in seen:
seen.add(w)
stack.append(w)
return seen
return any(u in reach(v) for u, v in arcs)
def test_acyclic_graphs():
"""graphs without a directed cycle give an empty list"""
assert find_cycle(4, [(0, 1), (1, 2), (0, 2), (2, 3)]) == []
assert find_cycle(3, []) == []
assert find_cycle(2, [(0, 1), (0, 1)]) == []
def test_small_cycles():
"""a loop, a two-vertex cycle and a triangle"""
assert find_cycle(3, [(0, 1), (2, 2)]) == [2]
check_cycle([(0, 1), (1, 0)], find_cycle(2, [(0, 1), (1, 0)]))
arcs = [(0, 1), (1, 2), (2, 0), (2, 3)]
check_cycle(arcs, find_cycle(4, arcs))
def test_cycle_found_late():
"""the only cycle hangs off vertex 5, which no earlier vertex reaches"""
arcs = [(0, 1), (1, 2), (3, 4), (5, 6), (6, 7), (7, 5), (7, 4)]
cycle = find_cycle(8, arcs)
check_cycle(arcs, cycle)
assert sorted(cycle) == [5, 6, 7]
def test_random_graphs():
"""300 random graphs: a cycle exactly when a slow test finds one, and every cycle is real"""
rng = random.Random(12)
for _ in range(300):
n = rng.randint(1, 9)
arcs = list({(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 14))})
rng.shuffle(arcs)
cycle = find_cycle(n, arcs)
if slow_has_cycle(n, arcs):
check_cycle(arcs, cycle)
else:
assert cycle == [], (n, arcs, cycle)
def test_long_chain():
"""a chain 0 -> 1 -> ... -> 99,999 closed by the arc 99,999 -> 0: the cycle has all 100,000 vertices"""
n = 100_000
arcs = [(i, i + 1) for i in range(n - 1)] + [(n - 1, 0)]
cycle = find_cycle(n, arcs)
assert len(cycle) == n
check_cycle(arcs, cycle)
assert find_cycle(n, arcs[:-1]) == []JavaScript · Starter code · cycle.mjs
/** One directed cycle [c0, ..., ck] (ck has an arc back to c0), or [] if the graph has none. */
export function findCycle(n, arcs) {
throw new Error('write findCycle');
}The sample tests · cycle.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { findCycle } from './cycle.mjs';
function checkCycle(arcs, cycle) {
const have = new Set(arcs.map(([u, v]) => `${u},${v}`));
assert.ok(cycle.length > 0 && new Set(cycle).size === cycle.length, `distinct vertices: ${JSON.stringify(cycle.slice(0, 10))}`);
for (let i = 0; i < cycle.length; i++) {
const u = cycle[i], w = cycle[(i + 1) % cycle.length];
assert.ok(have.has(`${u},${w}`), `an arc ${u} -> ${w}`);
}
}
function slowHasCycle(n, arcs) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of arcs) adj[u].push(v);
const reach = (s) => {
const seen = new Set([s]);
const stack = [s];
while (stack.length) for (const w of adj[stack.pop()]) if (!seen.has(w)) { seen.add(w); stack.push(w); }
return seen;
};
return arcs.some(([u, v]) => reach(v).has(u));
}
test('graphs without a directed cycle give an empty list', () => {
assert.deepEqual(findCycle(4, [[0, 1], [1, 2], [0, 2], [2, 3]]), []);
assert.deepEqual(findCycle(3, []), []);
assert.deepEqual(findCycle(2, [[0, 1], [0, 1]]), []);
});
test('a loop, a two-vertex cycle and a triangle', () => {
assert.deepEqual(findCycle(3, [[0, 1], [2, 2]]), [2]);
checkCycle([[0, 1], [1, 0]], findCycle(2, [[0, 1], [1, 0]]));
const arcs = [[0, 1], [1, 2], [2, 0], [2, 3]];
checkCycle(arcs, findCycle(4, arcs));
});
test('the only cycle hangs off vertex 5, which no earlier vertex reaches', () => {
const arcs = [[0, 1], [1, 2], [3, 4], [5, 6], [6, 7], [7, 5], [7, 4]];
const cycle = findCycle(8, arcs);
checkCycle(arcs, cycle);
assert.deepEqual([...cycle].sort((a, b) => a - b), [5, 6, 7]);
});
test('300 random graphs: a cycle exactly when a slow test finds one, and every cycle is real', () => {
let seed = 12;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
for (let k = 0; k < 300; k++) {
const n = 1 + Math.floor(random() * 9);
const keys = new Set();
const count = Math.floor(random() * 15);
for (let i = 0; i < count; i++) keys.add(`${Math.floor(random() * n)},${Math.floor(random() * n)}`);
const arcs = [...keys].map((s) => s.split(',').map(Number));
const cycle = findCycle(n, arcs);
if (slowHasCycle(n, arcs)) checkCycle(arcs, cycle);
else assert.deepEqual(cycle, [], JSON.stringify([n, arcs]));
}
});
test('a chain 0 -> 1 -> ... -> 99,999 closed by the arc 99,999 -> 0: the cycle has all 100,000 vertices', () => {
const n = 100000;
const arcs = Array.from({ length: n - 1 }, (_, i) => [i, i + 1]);
arcs.push([n - 1, 0]);
const cycle = findCycle(n, arcs);
assert.equal(cycle.length, n);
checkCycle(arcs, cycle);
assert.deepEqual(findCycle(n, arcs.slice(0, -1)), []);
});A hint
Colour every vertex white (not reached), grey (on the current path) or black (finished), and run a DFS from every white vertex with an explicit stack. Keep a parent for each vertex you discover. When the search meets an arc u -> v with v grey, follow the parents from u back to v, then reverse that list: it is the cycle.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Why the colour rules are right, and the parallel-edge trap reproduced Pro: opens with a Pro, Premium or Ultimate pass
Each of the three checks is correct for a short reason, and each certificate can be read off the search’s own pointers. This part proves all three, then checks them on 6,000 random graphs, including the rule that fails on parallel edges.
In this part:
- Directed graphs: grey means ancestor, with the proof
- Undirected graphs: skip the arrival edge, not the parent
- Bipartite graphs: no odd cycle, and the odd cycle when there is one
1 runnable example (Python) · about 2 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Directed cycle detection in five languages, on 100,000 vertices Pro: opens with a Pro, Premium or Ultimate pass
The three-colour search with an explicit stack is the version to write in any language, because a recursive one goes as deep as the longest path. This part runs it in Python, JavaScript, Java, C++ and Go on one graph of 100,000 vertices, with and without the arc that closes its cycle, and checks every arc of the cycle each version returns.
In this part:
- The search in Python and JavaScript
- The search in Java, C++ and Go
- Edge cases and the bugs they catch
- Some cycle, not the shortest one, with numbers
2 runnable examples (Build and run all three, C++, Go, Java, JavaScript, Python) · about 2 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Union-find, Kahn's leftovers and graphlib, with a practice set Pro: opens with a Pro, Premium or Ultimate pass
DFS colours are not the only tool, and interviews often ask for a different one: detecting the first edge that closes a cycle while edges arrive, or reporting a cycle from a topological sort that got stuck. This part runs three alternatives on the lesson’s graphs, compares all four methods, and ends with a practice set with answers.
In this part:
- Three alternatives, run on the lesson’s graphs
- Practice set
1 runnable example (Python) · about 2 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Mid to senior
A monorepo of 12,000 modules and 90,000 imports must be checked for circular imports on every commit, in under a second, and the report must show a cycle a developer can fix. How do you find one, and how do you keep the reported cycle short?
-
Fresher to mid
A clinic must put each of 400 nurses on a day shift or a night shift so that no two nurses who must not work together share a shift; there are 3,000 such pairs. Decide whether it is possible, and when it is not, what you show the manager.
-
Mid to senior
A network team lays 50,000 cables one at a time between 20,000 sites and wants an alert the moment a new cable closes a loop. Compare running a DFS after every cable with union-find, with numbers, and say what each can report.
Key takeaways
- In an undirected graph, reaching a visited vertex by any edge other than the arrival edge closes a cycle; track the edge, not the parent vertex.
- In a directed graph, use three colours: only an arc into a grey vertex, one on the current path, closes a cycle.
- A graph is bipartite exactly when it has no odd cycle; BFS colouring finds the two sides or an odd cycle.
- Return the cycle, not just yes or no: parent pointers give it, and anyone can check it arc by arc.
References
- Depth-first search and linear graph algorithms (R. E. Tarjan, SIAM Journal on Computing 1(2), 1972) (Society for Industrial and Applied Mathematics (SIAM))
- Dictionary of Algorithms and Data Structures: cycle (National Institute of Standards and Technology (NIST))
- Dictionary of Algorithms and Data Structures: bipartite graph (National Institute of Standards and Technology (NIST))
- Dictionary of Algorithms and Data Structures: multigraph (National Institute of Standards and Technology (NIST))
- Topological sorting of large networks (A. B. Kahn, Communications of the ACM 5(11), 1962) (Association for Computing Machinery (ACM))
- An improved equivalence algorithm (B. A. Galler and M. J. Fischer, Communications of the ACM 7(5), 1964) (Association for Computing Machinery (ACM))
- graphlib: functionality to operate with graph-like structures (Python Software Foundation)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027 organising institute))
- ACM/IEEE-CS/AAAI Computer Science Curricula 2023: Algorithmic Foundations (AL) (ACM, IEEE Computer Society and AAAI)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress