These are the graph problems that show up in senior-level interviews. They build on everything we’ve covered — BFS, DFS, Union-Find — and add a layer of complexity. Let’s break them down one at a time.
Cycle Detection in Directed Graphs
In a directed graph, we detect cycles using DFS with three states (also called 3-color marking):
- White (0) — Not visited yet
- Gray (1) — Currently in the recursion stack (being explored)
- Black (2) — Fully processed (all descendants explored)
If we encounter a gray node during DFS, we’ve found a cycle. That gray node is an ancestor in our current path, meaning we’ve looped back to it.
// Detect cycle in directed graph (3-color DFS)
function hasCycle(graph, n) {
const color = Array(n).fill(0); // 0=white, 1=gray, 2=black
function dfs(node) {
color[node] = 1; // mark gray (in progress)
for (const neighbor of graph[node]) {
if (color[neighbor] === 1) return true; // gray = cycle!
if (color[neighbor] === 0 && dfs(neighbor)) return true;
}
color[node] = 2; // mark black (done)
return false;
}
for (let i = 0; i < n; i++)
if (color[i] === 0 && dfs(i)) return true;
return false;
}# Detect cycle in directed graph (3-color DFS)
def has_cycle(graph, n):
color = [0] * n # 0=white, 1=gray, 2=black
def dfs(node):
color[node] = 1 # mark gray (in progress)
for neighbor in graph[node]:
if color[neighbor] == 1: # gray = cycle!
return True
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2 # mark black (done)
return False
return any(color[i] == 0 and dfs(i) for i in range(n))// Detect cycle in directed graph (3-color DFS)
boolean hasCycle(List<List<Integer>> graph, int n) {
int[] color = new int[n]; // 0=white, 1=gray, 2=black
for (int i = 0; i < n; i++)
if (color[i] == 0 && dfs(graph, i, color)) return true;
return false;
}
boolean dfs(List<List<Integer>> graph, int node, int[] color) {
color[node] = 1; // gray
for (int neighbor : graph.get(node)) {
if (color[neighbor] == 1) return true; // cycle!
if (color[neighbor] == 0 && dfs(graph, neighbor, color)) return true;
}
color[node] = 2; // black
return false;
}Cycle Detection in Undirected Graphs
For undirected graphs, it’s simpler. During DFS, if we visit a node that’s already been visited and it’s not our parent, we found a cycle.
// Detect cycle in undirected graph
function hasCycleUndirected(graph, n) {
const visited = new Set();
function dfs(node, parent) {
visited.add(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
if (dfs(neighbor, node)) return true;
} else if (neighbor !== parent) {
return true; // visited and not parent = cycle!
}
}
return false;
}
for (let i = 0; i < n; i++)
if (!visited.has(i) && dfs(i, -1)) return true;
return false;
}# Detect cycle in undirected graph
def has_cycle_undirected(graph, n):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # visited and not parent = cycle!
return False
return any(i not in visited and dfs(i, -1) for i in range(n))// Detect cycle in undirected graph
boolean hasCycleUndirected(List<List<Integer>> graph, int n) {
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++)
if (!visited[i] && dfs(graph, i, -1, visited)) return true;
return false;
}
boolean dfs(List<List<Integer>> graph, int node, int parent, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (dfs(graph, neighbor, node, visited)) return true;
} else if (neighbor != parent) return true; // cycle!
}
return false;
}Bipartite Check (Graph 2-Coloring)
A graph is bipartite if we can color every node with one of two colors such that no two adjacent nodes share the same color. In simple language, can we split all nodes into two teams where no one on the same team is connected?
This shows up as: “Is this graph 2-colorable?” or “Can we divide into two groups?”
We use BFS and try to assign alternating colors. If we find a neighbor with the same color as the current node, it’s not bipartite.
// Check if graph is bipartite using BFS
function isBipartite(graph, n) {
const color = Array(n).fill(-1); // -1 = uncolored
for (let i = 0; i < n; i++) {
if (color[i] !== -1) continue; // already colored
color[i] = 0;
const queue = [i];
while (queue.length > 0) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node]; // alternate color
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false; // same color = not bipartite
}
}
}
}
return true;
}# Check if graph is bipartite using BFS
from collections import deque
def is_bipartite(graph, n):
color = [-1] * n # -1 = uncolored
for i in range(n):
if color[i] != -1:
continue
color[i] = 0
queue = deque([i])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if color[neighbor] == -1:
color[neighbor] = 1 - color[node] # alternate
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False # not bipartite
return True// Check if graph is bipartite using BFS
boolean isBipartite(List<List<Integer>> graph, int n) {
int[] color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] != -1) continue;
color[i] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[node];
queue.add(neighbor);
} else if (color[neighbor] == color[node]) return false;
}
}
}
return true;
}Minimum Spanning Tree (Kruskal’s)
A Minimum Spanning Tree (MST) connects all nodes in a weighted undirected graph with the minimum total edge weight, using exactly V-1 edges and no cycles.
In simple language, imagine connecting all cities with roads. MST gives us the cheapest way to connect everyone without any redundant roads.
Kruskal’s Algorithm:
- Sort all edges by weight
- Process edges from lightest to heaviest
- Add an edge if it doesn’t create a cycle (use Union-Find to check!)
- Stop when we have V-1 edges
// Kruskal's MST using Union-Find
function kruskalMST(n, edges) {
edges.sort((a, b) => a[2] - b[2]); // sort by weight
const uf = new UnionFind(n); // from previous topic
let totalWeight = 0;
const mstEdges = [];
for (const [u, v, w] of edges) {
if (uf.union(u, v)) { // no cycle? add it
totalWeight += w;
mstEdges.push([u, v, w]);
if (mstEdges.length === n - 1) break; // MST complete
}
}
return { totalWeight, mstEdges };
}# Kruskal's MST using Union-Find
def kruskal_mst(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
uf = UnionFind(n) # from previous topic
total_weight = 0
mst_edges = []
for u, v, w in edges:
if uf.union(u, v): # no cycle? add it
total_weight += w
mst_edges.append((u, v, w))
if len(mst_edges) == n - 1: # MST complete
break
return total_weight, mst_edges// Kruskal's MST using Union-Find
int kruskalMST(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]); // sort by weight
UnionFind uf = new UnionFind(n); // from previous topic
int totalWeight = 0, edgeCount = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) { // no cycle? add it
totalWeight += e[2];
if (++edgeCount == n - 1) break; // MST complete
}
}
return totalWeight;
}Notice how Kruskal’s is basically Union-Find doing the heavy lifting. We sort edges, then greedily pick the lightest ones that don’t create cycles.
When These Come Up in Interviews
Complexity Summary
| Algorithm | Time | Space |
|---|---|---|
| Cycle Detection (directed) | O(V + E) | O(V) |
| Cycle Detection (undirected) | O(V + E) | O(V) |
| Bipartite Check | O(V + E) | O(V) |
| Kruskal’s MST | O(E log E) | O(V) |
These are the capstone graph problems. If we can comfortably code cycle detection, bipartite checking, and Kruskal’s MST, we’re well-prepared for even senior-level graph questions. Each one is really just a clever application of DFS, BFS, or Union-Find that we already know.