Chapter 20
Graphs (Basics) in Java
Java Data Structures & Algorithms Series
A Graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles,
multiple paths between nodes, and no single root. They model real-world systems like maps, social
networks, internet routing, and dependency resolution.
1 Graph Terminology
0 ——— 1
| / |
| / |
| / |
2 ——— 3 ——— 4
Term Meaning
Vertex (Node) A point in the graph (0, 1, 2, 3, 4)
Edge Connection between two vertices
Degree Number of edges connected to a vertex
Path Sequence of vertices connected by edges
Cycle Path that starts and ends at the same vertex
Connected Graph Every vertex reachable from every other
Component A connected subgraph
Weighted Graph Edges have associated costs/distances
Directed Graph Edges have direction (one-way)
2 Types of Graphs
Undirected: Directed: Weighted:
0 — 1 0 → 1 0 —5— 1
| | ↑ ↓ | |
2 — 3 3 ← 2 3 2 4
\—1—/
Type Description Example
Undirected Edges go both ways Facebook friends
Directed (Digraph) Edges are one-way Twitter follows
Weighted Edges have costs Google Maps
Unweighted All edges equal Social network
Cyclic Contains at least one cycle Road network
Acyclic No cycles (DAG if directed) Task dependencies
3 Graph Representations in Java
Representation 1 — Adjacency List (Most Common ✅)
Best for sparse graphs (few edges). Space: O(V + E).
import [Link].*;
// For undirected unweighted graph
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
// Initialize
for (int i = 0; i < V; i++) [Link](new ArrayList<>());
// Add edges (undirected)
[Link](0).add(1); [Link](1).add(0);
[Link](0).add(2); [Link](2).add(0);
[Link](1).add(2); [Link](2).add(1);
[Link](1).add(3); [Link](3).add(1);
[Link](2).add(3); [Link](3).add(2);
[Link](3).add(4); [Link](4).add(3);
// Print adjacency list
for (int i = 0; i < V; i++)
[Link]("Node " + i + " → " + [Link](i));
// Node 0 → [1, 2]
// Node 1 → [0, 2, 3]
// Node 2 → [0, 1, 3]
// Node 3 → [1, 2, 4]
// Node 4 → [3]
Representation 2 — Adjacency Matrix
Best for dense graphs (many edges). Space: O(V²).
int V = 5;
int[][] matrix = new int[V][V];
// Add edge between 0 and 1
matrix[0][1] = 1;
matrix[1][0] = 1; // for undirected
// Check if edge exists between u and v
boolean hasEdge = matrix[u][v] == 1; // O(1) lookup
// For weighted graph, store weight instead of 1
matrix[0][1] = 5; // edge 0→1 has weight 5
Representation 3 — Edge List
Simple list of all edges. Best for algorithms like Kruskal's MST.
int[][] edges = {
{0, 1}, // edge between 0 and 1
{0, 2},
{1, 3},
{2, 3},
{3, 4}
};
Which to Use?
Criteria Adjacency List Adjacency Matrix
Space O(V + E) O(V²)
Add edge O(1) O(1)
Check edge O(degree) O(1)
Get neighbors O(degree) O(V)
Best for Sparse graphs Dense graphs
4 BFS — Breadth First Search
BFS explores level by level using a Queue. Finds shortest path in unweighted graphs.
Graph: 0 — 1 — 3
| |
2 — 4
BFS from 0: [0, 1, 2, 3, 4]
public static List<Integer> bfs(List<List<Integer>> adj, int start, int V) {
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
[Link](start);
visited[start] = true;
while (![Link]()) {
int node = [Link]();
[Link](node);
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
return result;
}
// Time: O(V + E) | Space: O(V)
BFS Shortest Path (Unweighted)
public static int[] shortestPath(List<List<Integer>> adj, int src, int V) {
int[] dist = new int[V];
[Link](dist, -1);
dist[src] = 0;
Queue<Integer> queue = new LinkedList<>();
[Link](src);
while (![Link]()) {
int node = [Link]();
for (int neighbor : [Link](node)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
[Link](neighbor);
}
}
}
return dist;
}
// dist[i] = shortest distance from src to i
// Time: O(V + E) | Space: O(V)
5 DFS — Depth First Search
DFS explores as deep as possible before backtracking using a Stack (or recursion).
Graph: 0 — 1 — 3
| |
2 — 4
DFS from 0: [0, 1, 3, 4, 2] (order depends on adjacency list)
Recursive DFS
public static void dfsRecursive(List<List<Integer>> adj,
int node, boolean[] visited,
List<Integer> result) {
visited[node] = true;
[Link](node);
for (int neighbor : [Link](node)) {
if (!visited[neighbor])
dfsRecursive(adj, neighbor, visited, result);
}
}
public static List<Integer> dfs(List<List<Integer>> adj, int start, int V) {
boolean[] visited = new boolean[V];
List<Integer> result = new ArrayList<>();
dfsRecursive(adj, start, visited, result);
return result;
}
// Time: O(V + E) | Space: O(V) — recursion stack
Iterative DFS (Using Stack)
public static List<Integer> dfsIterative(List<List<Integer>> adj, int start, int V)
{
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
[Link](start);
while (![Link]()) {
int node = [Link]();
if (visited[node]) continue;
visited[node] = true;
[Link](node);
List<Integer> neighbors = [Link](node);
for (int i = [Link]() - 1; i >= 0; i--)
if (!visited[[Link](i)]) [Link]([Link](i));
}
return result;
}
// Time: O(V + E) | Space: O(V)
6 BFS vs DFS — When to Use Which?
Criteria BFS DFS
Data Structure Queue Stack / Recursion
Traversal Level by level Deep first
Shortest Path ✅ Guaranteed (unweighted) ❌ Not guaranteed
Cycle Detection ✅ Yes ✅ Yes
Connected Components ✅ Yes ✅ Yes
Memory O(width) — bad for wide O(depth) — bad for deep
Best For Shortest path, level problems Topological sort, backtracking
7 Key Graph Problems
🔑 Number of Connected Components
public static int countComponents(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V];
int components = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfsRecursive(adj, i, visited, new ArrayList<>());
components++;
}
}
return components;
}
// Time: O(V + E) | Space: O(V)
🔑 Number of Islands (2D Grid BFS)
public static int numIslands(char[][] grid) {
if (grid == null || [Link] == 0) return 0;
int rows = [Link], cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
bfsIsland(grid, r, c);
}
}
}
return islands;
}
private static void bfsIsland(char[][] grid, int r, int c) {
int rows = [Link], cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
[Link](new int[]{r, c});
grid[r][c] = '0';
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (![Link]()) {
int[] curr = [Link]();
for (int[] d : dirs) {
int nr = curr[0] + d[0], nc = curr[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1')
{
[Link](new int[]{nr, nc});
grid[nr][nc] = '0';
}
}
}
}
// Time: O(m×n) | Space: O(m×n)
🔑 Detect Cycle in Undirected Graph
public static boolean hasCycleUndirected(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (bfsCycleCheck(adj, i, visited)) return true;
}
}
return false;
}
private static boolean bfsCycleCheck(List<List<Integer>> adj,
int src, boolean[] visited) {
Queue<int[]> queue = new LinkedList<>(); // [node, parent]
[Link](new int[]{src, -1});
visited[src] = true;
while (![Link]()) {
int[] curr = [Link]();
int node = curr[0], parent = curr[1];
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](new int[]{neighbor, node});
} else if (neighbor != parent) {
return true; // cycle found!
}
}
}
return false;
}
// Time: O(V + E) | Space: O(V)
🔑 Flood Fill (Paint an Area)
public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
int originalColor = image[sr][sc];
if (originalColor == color) return image;
fill(image, sr, sc, originalColor, color);
return image;
}
private static void fill(int[][] image, int r, int c, int oldColor, int newColor) {
int rows = [Link], cols = image[0].length;
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (image[r][c] != oldColor) return;
image[r][c] = newColor;
fill(image, r+1, c, oldColor, newColor);
fill(image, r-1, c, oldColor, newColor);
fill(image, r, c+1, oldColor, newColor);
fill(image, r, c-1, oldColor, newColor);
}
// Time: O(m×n) | Space: O(m×n)
8 Full Runnable Java Program
import [Link].*;
public class Chapter20Graphs {
public static void main(String[] args) {
int V = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) [Link](new ArrayList<>());
// Build graph: 0-1-2-3, 0-2, 3-4 (5 is isolated)
addEdge(adj, 0, 1); addEdge(adj, 0, 2);
addEdge(adj, 1, 2); addEdge(adj, 1, 3);
addEdge(adj, 2, 3); addEdge(adj, 3, 4);
[Link]("BFS from 0: " + bfs(adj, 0, V));
[Link]("DFS from 0: " + dfs(adj, 0, V));
int[] dist = shortestPath(adj, 0, V);
[Link]("Shortest distances from 0: " + [Link](dist));
[Link]("Components: " + countComponents(adj, V)); // 2
[Link]("Has Cycle: " + hasCycleUndirected(adj, V)); // true
char[][] grid = {
{'1','1','0','0'},
{'1','0','0','1'},
{'0','0','1','1'}
};
[Link]("Islands: " + numIslands(grid)); // 3
}
static void addEdge(List<List<Integer>> adj, int u, int v) {
[Link](u).add(v); [Link](v).add(u);
}
static List<Integer> bfs(List<List<Integer>> adj, int start, int V) {
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[V];
Queue<Integer> q = new LinkedList<>();
[Link](start); visited[start] = true;
while (![Link]()) {
int node = [Link](); [Link](node);
for (int n : [Link](node))
if (!visited[n]) { visited[n] = true; [Link](n); }
}
return result;
}
static List<Integer> dfs(List<List<Integer>> adj, int start, int V) {
boolean[] visited = new boolean[V];
List<Integer> result = new ArrayList<>();
dfsHelper(adj, start, visited, result);
return result;
}
static void dfsHelper(List<List<Integer>> adj, int node,
boolean[] visited, List<Integer> res) {
visited[node] = true; [Link](node);
for (int n : [Link](node))
if (!visited[n]) dfsHelper(adj, n, visited, res);
}
static int[] shortestPath(List<List<Integer>> adj, int src, int V) {
int[] dist = new int[V]; [Link](dist, -1); dist[src] = 0;
Queue<Integer> q = new LinkedList<>(); [Link](src);
while (![Link]()) {
int node = [Link]();
for (int n : [Link](node))
if (dist[n] == -1) { dist[n] = dist[node] + 1; [Link](n); }
}
return dist;
}
static int countComponents(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V]; int count = 0;
for (int i = 0; i < V; i++)
if (!visited[i]) { dfsHelper(adj, i, visited, new ArrayList<>()); count+
+; }
return count;
}
static boolean hasCycleUndirected(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++)
if (!visited[i] && bfsCycleCheck(adj, i, visited)) return true;
return false;
}
static boolean bfsCycleCheck(List<List<Integer>> adj, int src, boolean[]
visited) {
Queue<int[]> q = new LinkedList<>();
[Link](new int[]{src, -1}); visited[src] = true;
while (![Link]()) {
int[] curr = [Link](); int node = curr[0], parent = curr[1];
for (int n : [Link](node)) {
if (!visited[n]) { visited[n] = true; [Link](new int[]{n, node}); }
else if (n != parent) return true;
}
}
return false;
}
static int numIslands(char[][] grid) {
int islands = 0;
for (int r = 0; r < [Link]; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { islands++; sinkIsland(grid, r, c); }
return islands;
}
static void sinkIsland(char[][] grid, int r, int c) {
if (r < 0 || r >= [Link] || c < 0 || c >= grid[0].length
|| grid[r][c] != '1') return;
grid[r][c] = '0';
sinkIsland(grid, r+1, c); sinkIsland(grid, r-1, c);
sinkIsland(grid, r, c+1); sinkIsland(grid, r, c-1);
}
}
9 Practice Problems for Chapter 20
Solve in this order:
Difficulty Problem
Easy BFS and DFS traversal of a graph
Easy Number of islands (LeetCode #200)
Easy Flood fill (LeetCode #733)
Medium Number of connected components (LeetCode #323)
Medium Detect cycle in undirected graph (GFG)
Medium Rotten oranges — multi-source BFS (LeetCode
#994)
Medium Clone a graph (LeetCode #133)
Hard Word ladder — BFS on implicit graph (LeetCode
#127)
💡 Key Insight: Every graph problem follows the same skeleton — initialize visited array → pick a
traversal (BFS/DFS) → process neighbors.
The 4-directional grid pattern (up/down/left/right) seen in Number of Islands appears in dozens of
interview problems.
Next is Chapter 21 — Graphs Advanced, where you'll learn Topological Sort, Dijkstra's shortest
path, and Union-Find — the algorithms that power real-world systems like GPS navigation and
package dependency managers! 🚀