Chapter 21

Graphs (Advanced) in Java

Java Data Structures & Algorithms Series

This chapter covers the four most powerful graph algorithms used in real-world systems and
interviews — Topological Sort, Cycle Detection in Directed Graphs, Dijkstra's Shortest Path, and
Union-Find (DSU).

1 Topological Sort

Topological Sort orders vertices of a Directed Acyclic Graph (DAG) such that for every directed edge
u → v, vertex u comes before v. Used in task scheduling, build systems, and course prerequisites.

Example:
5 → 0 ← 4
↓ ↓
2 → 3 → 1

Valid Topological Orders: [5,4,2,3,1,0] or [4,5,2,3,1,0]

Method 1 — Kahn's Algorithm (BFS-based)

Uses in-degree (number of incoming edges). Start with nodes that have no prerequisites.

public static List<Integer> topoSortBFS(List<List<Integer>> adj, int V) {

int[] inDegree = new int[V];

// Calculate in-degree of every vertex

for (int u = 0; u < V; u++)
for (int v : [Link](u))
inDegree[v]++;

// Add all nodes with in-degree 0 to queue (no prerequisites)

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++)
if (inDegree[i] == 0) [Link](i);

List<Integer> result = new ArrayList<>();

while (![Link]()) {
int node = [Link]();
[Link](node);

// Reduce in-degree of neighbors

for (int neighbor : [Link](node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) // all prerequisites done
[Link](neighbor);
 }
}

// If result has all V nodes → valid DAG

// If result has < V nodes → cycle exists!
return [Link]() == V ? result : new ArrayList<>();
}

// Time: O(V + E) | Space: O(V)

Method 2 — DFS-based Topological Sort

Run DFS, push node to stack after visiting all its descendants.

public static List<Integer> topoSortDFS(List<List<Integer>> adj, int V) {

boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < V; i++)

if (!visited[i])
dfsTopoSort(adj, i, visited, stack);

List<Integer> result = new ArrayList<>();

while (![Link]()) [Link]([Link]());
return result;
}

private static void dfsTopoSort(List<List<Integer>> adj, int node,

boolean[] visited, Stack<Integer> stack) {
visited[node] = true;
for (int neighbor : [Link](node))
if (!visited[neighbor])
dfsTopoSort(adj, neighbor, visited, stack);
[Link](node); // push AFTER all descendants are processed
}

// Time: O(V + E) | Space: O(V)

2 Cycle Detection in Directed Graph

Undirected cycle detection uses parent tracking. For directed graphs, use a recursion stack to detect
back edges.

0 → 1 → 2
↑ ↓
└── 3 ← cycle: 1→2→3→1

DFS with Recursion Stack

public static boolean hasCycleDirected(List<List<Integer>> adj, int V) {

 boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V]; // nodes in current DFS path

for (int i = 0; i < V; i++)

if (!visited[i])
if (dfsCycleDirected(adj, i, visited, recStack)) return true;

return false;
}

private static boolean dfsCycleDirected(List<List<Integer>> adj, int node,

boolean[] visited, boolean[] recStack) {
visited[node] = true;
recStack[node] = true; // add to current path

for (int neighbor : [Link](node)) {

if (!visited[neighbor]) {
if (dfsCycleDirected(adj, neighbor, visited, recStack)) return true;
} else if (recStack[neighbor]) {
return true; // back edge found → cycle!
}
}

recStack[node] = false; // remove from current path (backtrack)

return false;
}

// Time: O(V + E) | Space: O(V)

Using Kahn's Algorithm (Simpler)

// If topological sort doesn't include all V vertices → cycle exists

public static boolean hasCycleKahn(List<List<Integer>> adj, int V) {
List<Integer> topo = topoSortBFS(adj, V);
return [Link]() != V;
}

3 Dijkstra's Shortest Path Algorithm

Finds the shortest path from a source to all vertices in a weighted graph (no negative weights). Uses
a Min-Heap — always expand the closest unvisited node.

Graph:
0 —1— 1
| |
4 2
| |
3 —1— 2

Shortest from 0: {0:0, 1:1, 2:3, 3:4}

import [Link].*;
public static int[] dijkstra(List<List<int[]>> adj, int src, int V) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;

// Min-heap: [distance, node]

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
[Link](new int[]{0, src});

while (![Link]()) {
int[] curr = [Link]();
int d = curr[0], node = curr[1];

if (d > dist[node]) continue; // stale entry, skip

for (int[] edge : [Link](node)) {

int neighbor = edge[0], weight = edge[1];
int newDist = dist[node] + weight;

if (newDist < dist[neighbor]) {

dist[neighbor] = newDist;
[Link](new int[]{newDist, neighbor});
}
}
}
return dist;
}

// Time: O((V + E) log V) | Space: O(V)

Build Weighted Adjacency List:

List<List<int[]>> adj = new ArrayList<>();

for (int i = 0; i < V; i++) [Link](new ArrayList<>());

// Directed edge u→v with weight w

[Link](u).add(new int[]{v, w});

// Undirected edge
[Link](u).add(new int[]{v, w});
[Link](v).add(new int[]{u, w});

Dijkstra — Print Actual Shortest Path

public static List<Integer> dijkstraPath(List<List<int[]>> adj,

int src, int dest, int V) {
int[] dist = new int[V];
int[] parent = new int[V];
[Link](dist, Integer.MAX_VALUE);
[Link](parent, -1);
dist[src] = 0;

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

[Link](new int[]{0, src});

while (![Link]()) {
 int[] curr = [Link]();
int d = curr[0], node = curr[1];
if (d > dist[node]) continue;

for (int[] edge : [Link](node)) {

int neighbor = edge[0], weight = edge[1];
if (dist[node] + weight < dist[neighbor]) {
dist[neighbor] = dist[node] + weight;
parent[neighbor] = node;
[Link](new int[]{dist[neighbor], neighbor});
}
}
}

// Reconstruct path from dest back to src

List<Integer> path = new ArrayList<>();
for (int at = dest; at != -1; at = parent[at]) [Link](at);
[Link](path);
return path;
}

4 Union-Find (Disjoint Set Union — DSU)

DSU tracks which elements belong to the same connected component. Supports two operations in
near O(1) with optimizations:

 find(x): Which component does x belong to?

 union(x, y): Merge components of x and y

class DSU {
int[] parent, rank;

DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i; // each node is its own parent
}

// Find with Path Compression — flattens tree for O(1) amortized

public int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}

// Union by Rank — attach smaller tree under larger tree

public boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false; // already in same component

if (rank[px] < rank[py]) parent[px] = py;

else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }

return true; // successfully merged

}
 public boolean connected(int x, int y) {
return find(x) == find(y);
}
}

// find: O(α(n)) ≈ O(1) | union: O(α(n)) ≈ O(1)

// α = inverse Ackermann function — practically constant

DSU — Detect Cycle in Undirected Graph

public static boolean hasCycleDSU(int[][] edges, int V) {

DSU dsu = new DSU(V);
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
// If u and v are already connected, adding this edge creates a cycle
if () return true;
}
return false;
}

DSU — Number of Components

public static int countComponentsDSU(int[][] edges, int V) {

DSU dsu = new DSU(V);
for (int[] edge : edges) [Link](edge[0], edge[1]);

Set<Integer> roots = new HashSet<>();

for (int i = 0; i < V; i++) [Link]([Link](i));
return [Link]();
}

5 Key Advanced Graph Problems

🔑 Course Schedule (Topological Sort)

// Can you finish all courses given prerequisites?

// [0,1] means "take 1 before 0"
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) [Link](new ArrayList<>());
for (int[] pre : prerequisites) [Link](pre[1]).add(pre[0]);

List<Integer> topo = topoSortBFS(adj, numCourses);

return [Link]() == numCourses; // true if no cycle
}

🔑 Network Delay Time (Dijkstra)

// Minimum time for signal to reach all nodes from source K

public static int networkDelayTime(int[][] times, int n, int k) {
 List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) [Link](new ArrayList<>());
for (int[] t : times) [Link](t[0]).add(new int[]{t[1], t[2]});

int[] dist = dijkstra(adj, k, n + 1);

int maxDist = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1; // unreachable
maxDist = [Link](maxDist, dist[i]);
}
return maxDist;
}

🔑 Redundant Connection (DSU)

// Find the edge that creates a cycle — remove it

public static int[] findRedundantConnection(int[][] edges) {
int n = [Link];
DSU dsu = new DSU(n + 1);

for (int[] edge : edges) {

// If u and v already connected, this edge is redundant
if ()
return edge;
}
return new int[]{};
}

6 Algorithm Comparison

Algorithm Type Time Use Case

BFS Unweighted O(V+E) Shortest path
(unweighted)
DFS Any O(V+E) Cycle detect, topological
sort
Kahn's (Topo) DAG O(V+E) Task scheduling,
prerequisites
Dijkstra Weighted O((V+E) log V) Shortest path (non-
negative weights)
Union-Find Any O(α(n)) ≈ O(1) Connected components,
cycle detect

7 Full Runnable Java Program

import [Link].*;

public class Chapter21GraphsAdvanced {

public static void main(String[] args) {

int V = 6;

// --- Topological Sort ---

List<List<Integer>> dag = new ArrayList<>();
 for (int i = 0; i < V; i++) [Link](new ArrayList<>());
[Link](5).add(0); [Link](5).add(2);
[Link](4).add(0); [Link](4).add(1);
[Link](2).add(3); [Link](3).add(1);
[Link]("Topo Sort (BFS): " + topoSortBFS(dag, V));
[Link]("Topo Sort (DFS): " + topoSortDFS(dag, V));

// --- Cycle Detection Directed ---

List<List<Integer>> cycleGraph = new ArrayList<>();
for (int i = 0; i < 4; i++) [Link](new ArrayList<>());
[Link](0).add(1); [Link](1).add(2);
[Link](2).add(3); [Link](3).add(1); // cycle!
[Link]("Directed Cycle: " + hasCycleDirected(cycleGraph, 4));

// --- Dijkstra ---

int W = 5;
List<List<int[]>> wadj = new ArrayList<>();
for (int i = 0; i < W; i++) [Link](new ArrayList<>());
[Link](0).add(new int[]{1, 10}); [Link](0).add(new int[]{2, 3});
[Link](1).add(new int[]{3, 2}); [Link](2).add(new int[]{1, 4});
[Link](2).add(new int[]{3, 8}); [Link](2).add(new int[]{4, 2});
[Link](3).add(new int[]{4, 5}); [Link](4).add(new int[]{3, 1});
[Link]("Dijkstra from 0: " + [Link](dijkstra(wadj, 0,
W)));

// --- DSU ---

DSU dsu = new DSU(5);
[Link](0, 1); [Link](1, 2); [Link](3, 4);
[Link]("0 and 2 connected: " + [Link](0, 2)); // true
[Link]("0 and 3 connected: " + [Link](0, 3)); // false

// --- Course Schedule ---

int[][] prereqs = {{1,0},{2,1},{3,2}};
[Link]("Can finish courses: " + canFinish(4, prereqs)); // true

// --- Redundant Connection ---

int[][] edges = {{1,2},{1,3},{2,3}};
[Link]("Redundant edge: " +
[Link](findRedundantConnection(edges)));
}

static List<Integer> topoSortBFS(List<List<Integer>> adj, int V) {

int[] inDeg = new int[V];
for (int u = 0; u < V; u++) for (int v : [Link](u)) inDeg[v]++;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < V; i++) if (inDeg[i] == 0) [Link](i);
List<Integer> res = new ArrayList<>();
while (![Link]()) {
int node = [Link](); [Link](node);
for (int n : [Link](node)) if (--inDeg[n] == 0) [Link](n);
}
return [Link]() == V ? res : new ArrayList<>();
}

static List<Integer> topoSortDFS(List<List<Integer>> adj, int V) {

boolean[] vis = new boolean[V]; Stack<Integer> stk = new Stack<>();
for (int i = 0; i < V; i++) if (!vis[i]) dfsT(adj, i, vis, stk);
List<Integer> res = new ArrayList<>();
while (![Link]()) [Link]([Link]());
return res;
}

static void dfsT(List<List<Integer>> adj, int node,

 boolean[] vis, Stack<Integer> stk) {
vis[node] = true;
for (int n : [Link](node)) if (!vis[n]) dfsT(adj, n, vis, stk);
[Link](node);
}

static boolean hasCycleDirected(List<List<Integer>> adj, int V) {

boolean[] vis = new boolean[V], rec = new boolean[V];
for (int i = 0; i < V; i++)
if (!vis[i] && dfsCycle(adj, i, vis, rec)) return true;
return false;
}

static boolean dfsCycle(List<List<Integer>> adj, int node,

boolean[] vis, boolean[] rec) {
vis[node] = true; rec[node] = true;
for (int n : [Link](node)) {
if (!vis[n] && dfsCycle(adj, n, vis, rec)) return true;
else if (rec[n]) return true;
}
rec[node] = false; return false;
}

static int[] dijkstra(List<List<int[]>> adj, int src, int V) {

int[] dist = new int[V]; [Link](dist, Integer.MAX_VALUE); dist[src] =
0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
[Link](new int[]{0, src});
while (![Link]()) {
int[] curr = [Link](); int d = curr[0], node = curr[1];
if (d > dist[node]) continue;
for (int[] edge : [Link](node)) {
int nb = edge[0], w = edge[1];
if (dist[node] + w < dist[nb]) {
dist[nb] = dist[node] + w;
[Link](new int[]{dist[nb], nb});
}
}
}
return dist;
}

static boolean canFinish(int n, int[][] prereqs) {

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) [Link](new ArrayList<>());
for (int[] p : prereqs) [Link](p[1]).add(p[0]);
return topoSortBFS(adj, n).size() == n;
}

static int[] findRedundantConnection(int[][] edges) {

DSU dsu = new DSU([Link] + 1);
for (int[] e : edges) if () return e;
return new int[]{};
}
}

class DSU {
int[] parent, rank;
DSU(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
 if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public boolean union(int x, int y) {
int px = find(x), py = find(y); if (px == py) return false;
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }
return true;
}
public boolean connected(int x, int y) { return find(x) == find(y); }
}

8 Practice Problems for Chapter 21

Solve in this order:

Difficulty Problem
Easy Topological sort of a DAG (GFG)
Medium Course Schedule I — can you finish? (LeetCode
#207)
Medium Course Schedule II — return order (LeetCode #210)
Medium Network delay time — Dijkstra (LeetCode #743)
Medium Cheapest flights within K stops (LeetCode #787)
Medium Redundant connection — DSU (LeetCode #684)
Medium Number of provinces — DSU (LeetCode #547)
Hard Alien dictionary — topological sort (LeetCode
#269)
Hard Word ladder II — BFS + backtrack (LeetCode #126)

💡 Key Insight: These four algorithms appear in system design interviews too —
• Dijkstra powers GPS routing
• Union-Find powers distributed systems consistency
• Topological Sort powers CI/CD pipeline dependency resolution

You've now completed the full Graph module!

Next is Chapter 22 — Dynamic Programming Basics, the most feared and most rewarding topic in
DSA. The secret? Every DP problem is just recursion + memoization. 🚀