Java solutions for graph problems — BFS and DFS, number of islands, rotten oranges, detecting cycles in directed and undirected graphs, topological sort (DFS and Kahn), course schedule, Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal and Prim MSTs, union-find, word ladder, clone graph, shortest path in a binary matrix, network delay time, alien dictionary, bipartite checks, and articulation points and bridges.
Published September 25, 2026
First model the graph: what are the nodes and edges? Directed or not? Weighted? Dense or sparse (adjacency list vs matrix)? Then pick the tool:
| Need | Algorithm | Complexity |
|---|---|---|
| Reachability / components | DFS or BFS, union-find | O(V+E) |
| Shortest path, unweighted | BFS | O(V+E) |
| Shortest path, non-negative weights | Dijkstra (heap) | O((V+E) log V) |
| Negative weights / detect negative cycle | Bellman-Ford | O(V·E) |
| All-pairs shortest paths | Floyd-Warshall | O(V³) |
| Ordering with dependencies | Topological sort | O(V+E) |
| Minimum spanning tree | Kruskal (+DSU) / Prim (+heap) | O(E log E) / O(E log V) |
Learn it in depth → Graph DFS & BFS
Short answer:
Both are O(V+E) with adjacency lists. Mark nodes visited when enqueuing in BFS, to avoid duplicates in the queue.
List<Integer> bfs(List<List<Integer>> g, int src) {
List<Integer> order = new ArrayList<>(); boolean[] seen = new boolean[g.size()];
Deque<Integer> q = new ArrayDeque<>(List.of(src)); seen[src] = true;
while (!q.isEmpty()) {
int u = q.poll(); order.add(u);
for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; q.add(v); }
}
return order;
}
void dfs(List<List<Integer>> g, int u, boolean[] seen, List<Integer> order) {
seen[u] = true; order.add(u);
for (int v : g.get(u)) if (!seen[v]) dfs(g, v, seen, order);
}
Short answer: Scan the grid; for each unvisited '1', count an island and flood-fill it (DFS or BFS), marking its cells as '0'. O(m·n). Union-find also works, and suits dynamic versions (Number of Islands II). (Practice)
int numIslands(char[][] g) {
int count = 0;
for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++)
if (g[r][c] == '1') { count++; sink(g, r, c); }
return count;
}
void sink(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0';
sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}
Short answer: Use multi-source BFS: enqueue all the rotten oranges at once (time 0), and spread level by level to the fresh neighbours; count the minutes by level. If fresh oranges remain, return −1. O(m·n). (Practice)
int orangesRotting(int[][] g) {
Deque<int[]> q = new ArrayDeque<>(); int fresh = 0, minutes = 0;
for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++) {
if (g[r][c] == 2) q.add(new int[]{r, c}); else if (g[r][c] == 1) fresh++;
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty() && fresh > 0) {
for (int i = q.size(); i > 0; i--) {
int[] cell = q.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && c >= 0 && r < g.length && c < g[0].length && g[r][c] == 1) {
g[r][c] = 2; fresh--; q.add(new int[]{r, c});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
Short answer:
boolean hasCycleDirected(List<List<Integer>> g) {
int[] color = new int[g.size()];
for (int u = 0; u < g.size(); u++) if (color[u] == 0 && dfsCycle(g, u, color)) return true;
return false;
}
boolean dfsCycle(List<List<Integer>> g, int u, int[] color) {
color[u] = 1;
for (int v : g.get(u)) {
if (color[v] == 1) return true;
if (color[v] == 0 && dfsCycle(g, v, color)) return true;
}
color[u] = 2;
return false;
}
boolean hasCycleUndirected(List<List<Integer>> g, int u, int parent, boolean[] seen) {
seen[u] = true;
for (int v : g.get(u)) {
if (!seen[v]) { if (hasCycleUndirected(g, v, u, seen)) return true; }
else if (v != parent) return true;
}
return false;
}
Short answer:
Both are O(V+E). Course schedule asks whether a valid ordering exists (a cycle check); Course Schedule II returns the order. (Course Schedule, Course Schedule II)
int[] findOrder(int n, int[][] prereq) {
List<List<Integer>> g = new ArrayList<>(); int[] indeg = new int[n];
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] p : prereq) { g.get(p[1]).add(p[0]); indeg[p[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
int[] order = new int[n]; int k = 0;
while (!q.isEmpty()) {
int u = q.poll(); order[k++] = u;
for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
}
return k == n ? order : new int[0]; // empty => cycle, impossible
}
Learn it in depth → Topological Sort
Short answer: It finds single-source shortest paths with non-negative weights, using a min-heap of (dist, node). Pop the closest node; skip stale entries (where the stored distance is less than the popped one); relax its edges. O((V+E) log V).
Network delay time is Dijkstra from k: the answer is the maximum of the shortest distances, or −1 if any node is unreachable.
int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
for (int[] t : times) g.get(t[0]).add(new int[]{t[1], t[2]});
int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[k] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{0, k});
while (!pq.isEmpty()) {
int[] cur = pq.poll(); int d = cur[0], u = cur[1];
if (d > dist[u]) continue; // stale entry
for (int[] e : g.get(u))
if (d + e[1] < dist[e[0]]) { dist[e[0]] = d + e[1]; pq.add(new int[]{dist[e[0]], e[0]}); }
}
int max = 0;
for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) return -1; max = Math.max(max, dist[i]); }
return max;
}
Common trap: Dijkstra gives wrong answers with negative edge weights. Use Bellman-Ford there.
Short answer: Relax every edge V−1 times (a shortest path has at most V−1 edges). If any edge still relaxes on the V-th pass, there's a negative cycle reachable from the source. O(V·E). It handles negative weights, and supports "at most K stops" variants (limit the iterations, copying the distance array each round).
int[] bellmanFord(int n, int[][] edges, int src) { // edges: {u, v, w}
int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
for (int i = 0; i < n - 1; i++)
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) throw new IllegalStateException("negative cycle");
return dist;
}
Short answer: All-pairs shortest paths by DP over the intermediate nodes: d[i][j] = min(d[i][j], d[i][k] + d[k][j]), for each k (in the outer loop). O(V³) time, O(V²) space. Negative cycles show up as d[i][i] < 0. It suits small, dense graphs (roughly V ≤ 400).
void floydWarshall(long[][] d) { // d[i][j] = weight or INF; d[i][i] = 0
int n = d.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
// use INF = Long.MAX_VALUE / 4 to avoid overflow when adding
Short answer:
class DSU {
private final int[] parent, rank;
DSU(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; }
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
boolean union(int a, int b) {
int ra = find(a), rb = find(b); if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra; if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}
int kruskal(int n, int[][] edges) { // {u, v, w}
Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
DSU dsu = new DSU(n); int cost = 0, used = 0;
for (int[] e : edges) if (dsu.union(e[0], e[1])) { cost += e[2]; if (++used == n - 1) break; }
return used == n - 1 ? cost : -1; // -1 => graph not connected
}
Learn it in depth → Union-Find
Short answer: Grow the tree from any node: a min-heap of edges crossing from the tree to the outside; repeatedly take the cheapest edge to an unvisited node. O(E log V). It's better than Kruskal for dense graphs (with an adjacency matrix, the O(V²) version needs no heap).
int prim(List<List<int[]>> g) { // g.get(u) = list of {v, w}
boolean[] in = new boolean[g.size()]; int cost = 0, count = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{0, 0});
while (!pq.isEmpty() && count < g.size()) {
int[] cur = pq.poll(); int u = cur[0];
if (in[u]) continue;
in[u] = true; cost += cur[1]; count++;
for (int[] e : g.get(u)) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
}
return count == g.size() ? cost : -1;
}
Short answer: Each word is a node; the edges connect words that differ by one letter. BFS from the start word gives the shortest transformation. To find neighbours quickly, try all 26 letters in each position (O(L·26) per word), and remove the visited words from the dictionary. Bidirectional BFS speeds it up a lot. (Word Ladder)
int ladderLength(String begin, String end, List<String> words) {
Set<String> dict = new HashSet<>(words); if (!dict.contains(end)) return 0;
Deque<String> q = new ArrayDeque<>(List.of(begin)); dict.remove(begin);
for (int steps = 1; !q.isEmpty(); steps++) {
for (int i = q.size(); i > 0; i--) {
char[] w = q.poll().toCharArray();
for (int p = 0; p < w.length; p++) {
char orig = w[p];
for (char c = 'a'; c <= 'z'; c++) {
w[p] = c; String next = new String(w);
if (next.equals(end)) return steps + 1;
if (dict.remove(next)) q.add(next);
}
w[p] = orig;
}
}
}
return 0;
}
Short answer: DFS or BFS with a map from each original node to its clone. Create a clone on first sight, and connect the neighbours through the map, which handles cycles. O(V+E). (Clone Graph)
Map<Node, Node> clones = new HashMap<>();
Node cloneGraph(Node n) {
if (n == null) return null;
if (clones.containsKey(n)) return clones.get(n);
Node copy = new Node(n.val); clones.put(n, copy);
for (Node nb : n.neighbors) copy.neighbors.add(cloneGraph(nb));
return copy;
}
Short answer: Use BFS from (0,0) over the 0 cells, with 8-directional moves; the first time you reach (n-1, n-1) gives the path length. Return −1 if the start or end is blocked. O(n²). (A* with a Chebyshev-distance heuristic can be faster.)
int shortestPathBinaryMatrix(int[][] g) {
int n = g.length; if (g[0][0] == 1 || g[n - 1][n - 1] == 1) return -1;
Deque<int[]> q = new ArrayDeque<>(); q.add(new int[]{0, 0, 1}); g[0][0] = 1;
while (!q.isEmpty()) {
int[] c = q.poll();
if (c[0] == n - 1 && c[1] == n - 1) return c[2];
for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) {
int r = c[0] + dr, col = c[1] + dc;
if (r >= 0 && col >= 0 && r < n && col < n && g[r][col] == 0) { g[r][col] = 1; q.add(new int[]{r, col, c[2] + 1}); }
}
}
return -1;
}
Short answer: Derive the ordering edges from adjacent words: the first differing characters give a → b. Invalid case: a word followed by its own prefix (like "abc" before "ab"). Then run a topological sort (Kahn's algorithm) over all the letters that appear. If there's a cycle, return "". O(total characters).
String alienOrder(String[] words) {
Map<Character, Set<Character>> g = new HashMap<>(); Map<Character, Integer> indeg = new HashMap<>();
for (String w : words) for (char c : w.toCharArray()) { g.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); }
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return "";
for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
char x = a.charAt(j), y = b.charAt(j);
if (x != y) { if (g.get(x).add(y)) indeg.merge(y, 1, Integer::sum); break; }
}
}
Deque<Character> q = new ArrayDeque<>();
indeg.forEach((c, d) -> { if (d == 0) q.add(c); });
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char c = q.poll(); sb.append(c);
for (char nx : g.get(c)) if (indeg.merge(nx, -1, Integer::sum) == 0) q.add(nx);
}
return sb.length() == indeg.size() ? sb.toString() : "";
}
Short answer: 2-colour it with BFS or DFS: give each neighbour the opposite colour. If an edge connects two nodes of the same colour, it's not bipartite. Check every component. O(V+E). (A graph is bipartite exactly when it has no odd-length cycle.)
boolean isBipartite(int[][] g) {
int[] color = new int[g.length]; // 0 = uncoloured, 1 / -1
for (int s = 0; s < g.length; s++) {
if (color[s] != 0) continue;
Deque<Integer> q = new ArrayDeque<>(List.of(s)); color[s] = 1;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g[u]) {
if (color[v] == color[u]) return false;
if (color[v] == 0) { color[v] = -color[u]; q.add(v); }
}
}
}
return true;
}
Short answer: Tarjan's algorithm uses DFS discovery times disc[u], and the low-link low[u] (the earliest discovery time reachable from u's subtree using one back edge).
low[v] > disc[u]. The subtree of v can't reach u or above without this edge.low[v] >= disc[u];O(V+E). They're used for finding single points of failure in networks.
int timer = 0; int[] disc, low; List<List<Integer>> bridges = new ArrayList<>();
void dfsBridges(List<List<Integer>> g, int u, int parent) {
disc[u] = low[u] = ++timer;
for (int v : g.get(u)) {
if (v == parent) continue;
if (disc[v] == 0) {
dfsBridges(g, v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.add(List.of(u, v));
} else low[u] = Math.min(low[u], disc[v]);
}
}
// init: disc = new int[n]; low = new int[n]; call dfsBridges for every unvisited node with parent -1
Q: Why does BFS give shortest paths only in unweighted graphs? A: BFS explores in order of the number of edges. With weights, a path with more edges can be cheaper, so you need Dijkstra (or 0-1 BFS with a deque when the weights are only 0 and 1).
Q: Why skip stale heap entries in Dijkstra instead of using decrease-key?
A: Java's PriorityQueue has no efficient decrease-key. Pushing a new entry and ignoring outdated ones on pop is simpler, with the same asymptotic cost.
Q: When would you use union-find instead of DFS? A: When edges arrive incrementally (dynamic connectivity), for Kruskal's algorithm, and for grouping problems (accounts merge, redundant connection), where near-O(1) merge and find operations beat repeated traversals.
Q: How do you avoid recursion depth problems in graph DFS?
A: Use an explicit stack for large graphs (for example, 10⁵+ nodes in a path-like shape), or increase the thread stack size by running the work in a Thread constructed with a larger stack.