Graph coloring, Eulerian and Hamiltonian paths, strongly connected components, articulation points and bridges. These are the problems that graph theory was invented to solve — and they still trip up experienced engineers.
AdvancedThis page covers a handful of graph algorithms that go beyond basic BFS/DFS traversals and shortest-path algorithms. Each solves a specific structural question about a graph. They come up in interviews at top companies (especially Google and Meta) and are essential in competitive programming.
Graph coloring assigns a label (called a "color") to each vertex (a node in the graph) such that no two adjacent vertices (nodes connected by an edge) share the same color. The minimum number of colors needed for a valid coloring is the chromatic number, usually written χ(G).
This problem has a surprisingly rich history. In 1852, Francis Guthrie noticed that the counties of England could be colored with just four colors such that no neighboring counties shared a color. He conjectured this was true for any map. The four-color theorem — that any planar graph (a graph that can be drawn on a plane without edge crossings) can be colored with at most 4 colors — wasn't proved until 1976, and the proof required a computer to check 1,936 configurations. It remains one of the most famous results in mathematics.
Practical uses of graph coloring:
An Eulerian path visits every edge exactly once. An Eulerian circuit (or Eulerian cycle) does the same but starts and ends at the same vertex. Named after Leonhard Euler, who in 1736 proved that the famous Königsberg bridge problem had no solution — making it arguably the first theorem in graph theory and the birth of the entire field.
The Königsberg problem: the city had four land masses connected by seven bridges. Could you walk a route crossing each bridge exactly once? Euler showed this was impossible because more than two land masses had an odd number of bridges (odd degree — the number of edges connected to a vertex).
The conditions are clean and easy to check:
A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit visits every vertex exactly once and returns to the start. Despite the superficial similarity to Eulerian paths (edges vs vertices), the computational difference is enormous.
Determining whether a Hamiltonian path exists is NP-complete — no known polynomial-time algorithm exists, and most computer scientists believe none ever will. The Traveling Salesman Problem (TSP), one of the most famous problems in all of computer science, is essentially "find the shortest Hamiltonian circuit in a weighted graph."
For small graphs (n ≤ 20), you can solve Hamiltonian path with bitmask DP in O(n² · 2n). For larger graphs, you need heuristics or approximation algorithms. The bitmask tracks which vertices have been visited: dp[mask][v] = "can we visit exactly the vertices in mask, ending at v?"
In a directed graph, a strongly connected component is a maximal group of vertices where every vertex can reach every other vertex through directed paths. "Maximal" means you can't add any more vertices and maintain the property.
Think of a website link graph. If page A links to page B, and page B (perhaps through a chain of other pages) links back to A, they're in the same SCC. Within an SCC, information can flow freely in any direction. Between SCCs, flow is one-way.
Once you find all SCCs, you can condense the graph: replace each SCC with a single super-node. The resulting graph is always a DAG (directed acyclic graph) — no cycles can exist between different SCCs, by definition. This condensation simplifies many problems because DAGs support topological sorting and straightforward DP.
Applications of SCCs:
An articulation point (or cut vertex) is a vertex whose removal disconnects the graph. A bridge (or cut edge) is an edge whose removal disconnects the graph. Both are found using a modified DFS in O(V + E) — essentially the same algorithm as Tarjan's SCC, but applied to undirected graphs.
These matter for network reliability. An articulation point is a single point of failure. A bridge is a single link whose failure splits the network. Identifying them is critical in network design, circuit analysis, and infrastructure planning.
The simplest coloring algorithm: process vertices one at a time. For each vertex, look at the colors assigned to its already-processed neighbors. Assign the smallest color (starting from 0) that none of them are using.
This greedy approach does not guarantee the minimum number of colors — that problem (finding the chromatic number) is NP-hard for general graphs. But it does guarantee at most Δ+1 colors, where Δ (Delta) is the maximum degree in the graph. Brooks' theorem tightens this: every connected graph can be colored with at most Δ colors, except for complete graphs and odd cycles.
The vertex processing order affects the result dramatically. The Welsh-Powell algorithm sorts vertices by degree in descending order before greedy coloring, which tends to produce better results. For bipartite graphs, you always need exactly 2 colors — and detecting bipartiteness is just BFS/DFS 2-coloring.
Tarjan's algorithm finds all SCCs in a single DFS traversal — O(V + E) time. It's elegant but tricky to understand, so let's go piece by piece.
Every node gets two numbers:
The algorithm maintains a stack of vertices in the current DFS path. When we finish processing a vertex v and find that low[v] == ids[v], that means v is the root of its SCC — no vertex in v's subtree can reach anything discovered before v. We pop everything off the stack down to and including v; that's one complete SCC.
Trace through a 5-node example: A→B, B→C, C→A, B→D, D→E:
Final SCCs: {A, B, C}, {D}, {E}. Correct — A, B, C form a cycle, while D and E are not part of any cycle.
Kosaraju's algorithm is conceptually simpler than Tarjan's:
Why does this work? In the original graph, vertices with later finish times can reach vertices with earlier finish times. In the reverse graph, this relationship flips. Processing in reverse finish order ensures that each DFS in the reverse graph captures exactly the vertices that can reach each other in both directions — which is the definition of an SCC.
Given a graph with an Eulerian circuit (all degrees even, connected), Hierholzer's algorithm constructs the circuit in O(E) time:
In practice, this is implemented with a stack and edge deletion. The "splicing" happens naturally when you use a stack-based DFS approach.
Found using Tarjan's bridge-finding algorithm (not the SCC one — similar idea, different context). During DFS on an undirected graph:
Coloring mode: click nodes to cycle colors. SCC mode: runs Tarjan's and highlights components.
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Greedy Coloring | O(V + E) | O(V) | Not optimal, uses ≤ Δ+1 colors |
| Optimal Coloring | NP-hard | — | Exact solution is exponential |
| Bipartite Check (2-color) | O(V + E) | O(V) | BFS or DFS |
| Tarjan's SCC | O(V + E) | O(V) | Single DFS pass |
| Kosaraju's SCC | O(V + E) | O(V + E) | Two DFS passes + reverse graph |
| Bridges (Tarjan's) | O(V + E) | O(V) | Modified DFS |
| Articulation Points | O(V + E) | O(V) | Modified DFS |
| Eulerian Circuit Check | O(V + E) | O(1) | Check degree parity + connectivity |
| Hierholzer's (Euler) | O(E) | O(E) | Constructs the circuit/path |
| Hamiltonian (bitmask DP) | O(n² · 2ⁿ) | O(n · 2ⁿ) | Practical for n ≤ 20 |
def tarjan_scc(graph):
"""Find all Strongly Connected Components using Tarjan's algorithm.
graph: dict of node -> [neighbors] (adjacency list for directed graph).
Returns list of SCCs, each SCC is a list of nodes.
Time: O(V + E), Space: O(V)."""
idx = [0] # mutable counter for discovery time
stack = [] # DFS stack of active nodes
on_stack = set() # O(1) lookup for "is node on stack?"
ids = {} # discovery time per node
low = {} # lowest reachable discovery time
sccs = [] # result: list of components
def dfs(v):
ids[v] = low[v] = idx[0]
idx[0] += 1
stack.append(v)
on_stack.add(v)
for w in graph.get(v, []):
if w not in ids:
# Tree edge: w hasn't been visited yet
dfs(w)
low[v] = min(low[v], low[w])
elif w in on_stack:
# Back edge: w is an ancestor in the current DFS path.
# It's in the same SCC candidate as v.
low[v] = min(low[v], ids[w])
# If w was visited but NOT on stack, it's in a
# completed SCC — don't update low[v].
# Root of SCC: no vertex in v's subtree can reach
# anything discovered before v.
if low[v] == ids[v]:
component = []
while True:
w = stack.pop()
on_stack.remove(w)
component.append(w)
if w == v:
break
sccs.append(component)
for v in graph:
if v not in ids:
dfs(v)
return sccs
# Example:
# graph = {'A':['B'], 'B':['C','D'], 'C':['A'], 'D':['E'], 'E':[]}
# tarjan_scc(graph) → [['E'], ['D'], ['C','B','A']]
def kosaraju_scc(graph):
"""Two-pass SCC algorithm. Conceptually simpler than Tarjan's.
1. DFS on original graph, record finish order.
2. DFS on reversed graph in reverse finish order.
Time: O(V + E), Space: O(V + E) for the reversed graph."""
# Pass 1: DFS on original graph, record finish order
visited = set()
finish_order = []
def dfs1(v):
visited.add(v)
for w in graph.get(v, []):
if w not in visited:
dfs1(w)
finish_order.append(v) # post-order
for v in graph:
if v not in visited:
dfs1(v)
# Build reverse graph
rev = {}
for v in graph:
rev.setdefault(v, [])
for w in graph[v]:
rev.setdefault(w, []).append(v)
# Pass 2: DFS on reverse graph in reverse finish order
visited.clear()
sccs = []
def dfs2(v, component):
visited.add(v)
component.append(v)
for w in rev.get(v, []):
if w not in visited:
dfs2(w, component)
for v in reversed(finish_order):
if v not in visited:
comp = []
dfs2(v, comp)
sccs.append(comp)
return sccs
function tarjanSCC(graph) {
let idx = 0;
const stack = [], onStack = new Set();
const ids = {}, low = {};
const sccs = [];
function dfs(v) {
ids[v] = low[v] = idx++;
stack.push(v);
onStack.add(v);
for (const w of (graph[v] || [])) {
if (ids[w] === undefined) {
dfs(w);
low[v] = Math.min(low[v], low[w]);
} else if (onStack.has(w)) {
low[v] = Math.min(low[v], ids[w]);
}
}
if (low[v] === ids[v]) {
const comp = [];
let w;
do {
w = stack.pop();
onStack.delete(w);
comp.push(w);
} while (w !== v);
sccs.push(comp);
}
}
for (const v in graph) {
if (ids[v] === undefined) dfs(v);
}
return sccs;
}
def greedy_color(graph):
"""Greedy graph coloring. Assigns smallest available color to each vertex.
graph: dict of node -> set/list of neighbors.
Returns dict of node -> color (0-indexed).
Guarantees at most max_degree + 1 colors."""
colors = {}
for node in graph:
# Gather colors used by already-colored neighbors
used = {colors[n] for n in graph[node] if n in colors}
# Assign smallest unused color
color = 0
while color in used:
color += 1
colors[node] = color
return colors
def is_bipartite(graph):
"""Check if graph is 2-colorable using BFS.
Equivalent to checking for odd-length cycles."""
color = {}
for start in graph:
if start in color:
continue
# BFS from start
queue = [start]
color[start] = 0
while queue:
next_queue = []
for node in queue:
for neighbor in graph[node]:
if neighbor not in color:
color[neighbor] = 1 - color[node]
next_queue.append(neighbor)
elif color[neighbor] == color[node]:
return False # odd cycle found
queue = next_queue
return True
def find_bridges(graph):
"""Find all bridges (cut edges) in an undirected graph.
A bridge is an edge whose removal disconnects the graph.
graph: dict of node -> list of neighbors.
Time: O(V + E)."""
timer = [0]
ids = {}
low = {}
bridges = []
def dfs(v, parent):
ids[v] = low[v] = timer[0]
timer[0] += 1
for w in graph.get(v, []):
if w == parent:
continue # don't go back on the edge we came from
if w not in ids:
dfs(w, v)
low[v] = min(low[v], low[w])
# Bridge condition: w's subtree can't reach
# anything at or above v
if low[w] > ids[v]:
bridges.append((v, w))
else:
low[v] = min(low[v], ids[w])
for v in graph:
if v not in ids:
dfs(v, -1)
return bridges
def find_articulation_points(graph):
"""Find all articulation points (cut vertices).
Time: O(V + E)."""
timer = [0]
ids = {}
low = {}
ap = set()
def dfs(v, parent):
ids[v] = low[v] = timer[0]
timer[0] += 1
children = 0
for w in graph.get(v, []):
if w == parent:
continue
if w not in ids:
children += 1
dfs(w, v)
low[v] = min(low[v], low[w])
# Non-root: AP if child can't escape above v
if parent != -1 and low[w] >= ids[v]:
ap.add(v)
else:
low[v] = min(low[v], ids[w])
# Root: AP if it has 2+ children in DFS tree
if parent == -1 and children >= 2:
ap.add(v)
for v in graph:
if v not in ids:
dfs(v, -1)
return ap
from collections import defaultdict
def find_euler_path(graph):
"""Find Eulerian path/circuit in a directed graph.
graph: dict of node -> list of neighbors (adjacency list).
Returns the path as a list of vertices, or empty if none exists.
For directed graphs:
- Circuit: every node has in_degree == out_degree
- Path: one node has out - in = 1 (start), one has in - out = 1 (end)"""
# Convert to mutable adjacency list with index tracking
adj = defaultdict(list)
in_deg = defaultdict(int)
out_deg = defaultdict(int)
for u in graph:
for v in graph[u]:
adj[u].append(v)
out_deg[u] += 1
in_deg[v] += 1
# Find start node
start = None
for node in set(list(in_deg.keys()) + list(out_deg.keys())):
if out_deg[node] - in_deg[node] == 1:
start = node
break
if start is None:
# Eulerian circuit — start anywhere with edges
for node in adj:
if adj[node]:
start = node
break
# Hierholzer's: DFS with edge deletion
stack = [start]
path = []
edge_idx = defaultdict(int) # tracks next unused edge for each node
while stack:
v = stack[-1]
if edge_idx[v] < len(adj[v]):
# Follow next unused edge
w = adj[v][edge_idx[v]]
edge_idx[v] += 1
stack.append(w)
else:
# No more edges from v — add to path (in reverse)
path.append(stack.pop())
path.reverse()
return path
In any package manager (npm, pip, cargo), circular dependencies between modules cause build failures. SCCs are the tool to detect and report them. If packages A, B, C form a cycle (A depends on B, B depends on C, C depends on A), they're in the same SCC. Any SCC with more than one node represents a circular dependency that needs to be broken.
def detect_circular_deps(packages):
"""Detect circular dependencies in a package dependency graph.
packages: dict of package_name -> [list of dependencies].
Returns list of circular dependency groups (SCCs with size > 1)."""
sccs = tarjan_scc(packages) # using our Tarjan implementation
circular = [scc for scc in sccs if len(scc) > 1]
if circular:
print("⚠️ Circular dependencies detected!")
for i, group in enumerate(circular):
print(f" Cycle {i+1}: {' → '.join(group)} → {group[0]}")
else:
print("✅ No circular dependencies.")
return circular
# Example: a real-world-ish package graph
packages = {
'auth': ['database', 'crypto'],
'database': ['logger'],
'logger': ['config'],
'config': ['auth'], # ← circular! auth → database → logger → config → auth
'crypto': [],
'api': ['auth', 'logger'],
'frontend': ['api']
}
detect_circular_deps(packages)
# Output:
# ⚠️ Circular dependencies detected!
# Cycle 1: auth → database → logger → config → auth
# The SCC condensation turns this into a DAG:
# {auth,database,logger,config} → crypto
# {auth,database,logger,config} ← api ← frontend
This exact approach is used by build tools. Webpack detects circular imports this way. Python's importlib warns about circular imports. Rust's cargo refuses to compile crates with cyclic dependencies. The underlying algorithm is always SCC detection.
| # | Problem | Difficulty | Key Concept |
|---|---|---|---|
| 785 | Is Graph Bipartite? | Medium | 2-coloring / BFS |
| 332 | Reconstruct Itinerary | Hard | Eulerian path (Hierholzer's) |
| 1192 | Critical Connections in a Network | Hard | Tarjan's bridges |
| 886 | Possible Bipartition | Medium | Graph coloring / bipartite |
| 943 | Find the Shortest Superstring | Hard | Hamiltonian path + bitmask DP |
| 2360 | Longest Cycle in a Graph | Hard | Cycle detection / functional graph |
| 2101 | Detonate the Maximum Bombs | Medium | Directed reachability / SCC ideas |
| 1557 | Min Vertices to Reach All Nodes | Medium | In-degree 0 in DAG (SCC condensation) |