Introduction to Graphs
Graph
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Unlike trees which have a hierarchical parent-child relationship, graphs can have any arbitrary connections between nodes, including cycles and multiple paths between the same pair of nodes. Graphs are incredibly versatile and used to model real-world networks like social connections (Facebook friends), transportation systems (roads between cities), computer networks (internet routing), and dependencies (course prerequisites). Every tree is a graph, but not every graph is a tree!
Undirected
Edges have no direction - if A connects to B, then B connects to A. Think: friendships on Facebook (mutual), roads that allow travel in both directions.
Directed
Edges have direction - A→B doesn't mean B→A. Think: Twitter follows (you can follow someone without them following you), one-way streets.
Weighted
Each edge has a cost, distance, or weight associated with it. Think: road distances between cities, flight ticket prices, or bandwidth capacity between network nodes.
Cyclic
Contains at least one cycle (path that returns to start). Acyclic graphs have no cycles - trees and DAGs (Directed Acyclic Graphs) are acyclic.
| Term | Definition | Example |
|---|---|---|
| Vertex (Node) | The fundamental unit of a graph, representing an entity such as a person, city, or data point. Vertices are typically labeled with numbers (0, 1, 2...) or names. | In a social network: each user is a vertex |
| Edge | A connection or link between two vertices. Edges can be directed (one-way) or undirected (two-way), and may carry weights representing cost, distance, or capacity. | A friendship between two users is an edge |
| Degree | The number of edges connected to a vertex. In directed graphs, we distinguish between in-degree (incoming edges) and out-degree (outgoing edges). | A user with 5 friends has degree 5 |
| Path | A sequence of vertices where each adjacent pair is connected by an edge. A simple path visits each vertex at most once. | NYC → Chicago → Denver → LA is a path |
| Cycle | A path that starts and ends at the same vertex, forming a closed loop. A graph without cycles is called acyclic. | A → B → C → A is a cycle of length 3 |
| Connected | A graph is connected if a path exists between every pair of vertices. If not connected, the graph has multiple connected components (isolated groups). | Internet: most computers are connected |
Practice Questions: Graph Fundamentals
Test your understanding with these hands-on exercises.
Problem: Given an edge list, write a method to count the number of unique vertices and edges in an undirected graph.
// Input: edges = [[0,1], [1,2], [2,0], [1,3]]
// Output: Vertices = 4, Edges = 4
public static int[] countVerticesAndEdges(int[][] edges) {
// Your code here
}Show Solution
public static int[] countVerticesAndEdges(int[][] edges) {
Set vertices = new HashSet<>();
for (int[] edge : edges) {
vertices.add(edge[0]);
vertices.add(edge[1]);
}
return new int[]{vertices.size(), edges.length};
}
// Test: countVerticesAndEdges(new int[][]{{0,1},{1,2},{2,0},{1,3}})
// Output: [4, 4] Problem: Given an adjacency list, calculate the degree (number of edges) for each vertex.
// Input: adj = [[1,2], [0,2,3], [0,1], [1]]
// Output: [2, 3, 2, 1] (degrees for vertices 0,1,2,3)
public static int[] calculateDegrees(List> adj) {
// Your code here
} Show Solution
public static int[] calculateDegrees(List> adj) {
int[] degrees = new int[adj.size()];
for (int i = 0; i < adj.size(); i++) {
degrees[i] = adj.get(i).size();
}
return degrees;
}
// For undirected: degree = size of neighbor list
// For directed: in-degree requires counting incoming edges Graph Representation
What is Graph Representation?
Graph Representation is how we store a graph in computer memory so we can efficiently perform operations like finding neighbors, checking if an edge exists, or traversing the entire graph. Just like you can write the same number as "5", "five", or "V", a graph can be represented in multiple ways - each with different strengths for different use cases.
Choosing the right representation is crucial for algorithm efficiency. Think of it like choosing between a phone book (alphabetical lookup) vs. a contact list (scroll through) - both store the same information but work better for different tasks. The two most common representations are Adjacency List (memory-efficient, great for sparse graphs) and Adjacency Matrix (fast edge lookup, great for dense graphs).
Adjacency List
Each vertex maintains a list of its neighbors. Like a contact list where each person has a list of their friends' names. Memory efficient - only stores edges that actually exist.
Best for: Sparse graphs (few edges), traversal algorithms, most real-world graphs (social networks, road maps).
Adjacency Matrix
A 2D table (V×V) where cell [i][j] tells if there's an edge from vertex i to j. Like a spreadsheet where rows and columns are vertices - check any intersection instantly!
Best for: Dense graphs (many edges), when you need O(1) edge lookup, weighted graphs, small graphs.
How to Choose?
Use Adjacency List when: E << V² (sparse graph), you need to iterate over neighbors frequently, memory is a concern.
Use Adjacency Matrix when: E ≈ V² (dense graph), you need instant edge existence check, the graph is small (under 1000 vertices).
Adjacency List (Preferred)
Basic Graph Structure
class Graph {
int V; // Number of vertices
List> adj;
Graph(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
} What's happening here?
We store the graph as a list of lists, where V holds how many vertices (nodes) our graph has, and adj is our "adjacency list" - think of it as a contact list for each vertex. In the constructor, we create V empty lists (one for each vertex from 0 to V-1), and later we'll fill these lists with each vertex's neighbors.
Real-world analogy: Imagine a phone book where each person has a list of their friends' phone numbers!
Adding Edges
// Add edge for undirected graph
void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u); // Remove this line for directed graph
}
// Get neighbors of a vertex
List getNeighbors(int v) {
return adj.get(v);
} What's happening here?
The addEdge(u, v) method creates a connection between vertex u and vertex v. When we call adj.get(u).add(v), we're saying "go to vertex u's friend list and add v", and adj.get(v).add(u) does the reverse. We add both directions because in an undirected graph, if A knows B, then B also knows A! For a directed graph (like one-way streets), you'd remove the second line to only add u→v, not v→u.
Example: Calling addEdge(0, 1) makes 0 and 1 neighbors. Now adj.get(0) contains [1] and adj.get(1) contains [0].
HashMap-Based Graph (Non-Consecutive Vertices)
Map> graph = new HashMap<>();
void addEdge(int u, int v) {
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
} When to use HashMap instead of ArrayList?
ArrayList requires indices 0, 1, 2, 3... but what if your vertices are 5, 100, or 999? That's where HashMap comes in! It maps any key (vertex ID) to its neighbor list, so you're not limited to consecutive numbers. The computeIfAbsent(u, k -> new ArrayList<>()) method means "if u doesn't exist, create an empty list for it, then add v". This approach is also useful when vertices are strings (like city names) or objects (like user IDs).
Example: Cities like "NYC", "LA", "Chicago" can't be used as array indices, but they work perfectly as HashMap keys!
Weighted Graph Adjacency List
List> weightedAdj = new ArrayList<>();
// Each int[] is {neighbor, weight}
weightedAdj.get(u).add(new int[]{v, weight}); Understanding Weighted Graphs
A weight is a cost, distance, or value associated with an edge (like road distance or ticket price). Instead of just storing the neighbor ID, we store int[]{neighbor, weight} - an array with 2 values. The expression new int[]{v, weight} creates a pair containing the destination vertex and the cost to reach it. To read it back, you'd do: int[] edge = weightedAdj.get(u).get(0); int neighbor = edge[0]; int weight = edge[1];
Real-world example: Flight routes! NYC→LA might cost $300, but NYC→Chicago only $150. We need to store these costs along with the connections.
Adjacency Matrix
Matrix Structure & Initialization
class GraphMatrix {
int V;
int[][] matrix;
GraphMatrix(int V) {
this.V = V;
matrix = new int[V][V]; // All zeros initially
}
}What's happening here?
We create a 2D array (table) of size V rows x V columns, where each cell matrix[i][j] represents "Is there an edge from vertex i to vertex j?". A value of 0 means no connection, while 1 means connected (or you can use the actual weight for weighted graphs). Initially all cells are 0 (no edges yet) since Java automatically initializes int arrays to 0.
Think of it as: A spreadsheet where rows and columns are vertices - put a 1 where two vertices are connected!
Adding and Checking Edges
// Add edge (use 1 for unweighted, actual weight for weighted)
void addEdge(int u, int v) {
matrix[u][v] = 1;
matrix[v][u] = 1; // Remove for directed graph
}
// Check if edge exists - O(1) lookup!
boolean hasEdge(int u, int v) {
return matrix[u][v] != 0;
}What's happening here?
The addEdge(u, v) method sets matrix[u][v] = 1 to mark "edge exists from u to v". For undirected graphs, we also set matrix[v][u] = 1 since the connection works both ways. The hasEdge(u, v) method simply checks if matrix[u][v] is not 0 - this gives us instant O(1) lookup because accessing an array by index is constant time with no searching needed.
Trade-off: Super fast edge lookup, but uses V² memory even if the graph is sparse (few edges). For 1000 vertices, that's 1 million cells!
Comparison: List vs Matrix
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Add Edge | O(1) | O(1) |
| Check Edge | O(degree) | O(1) |
| Best For | Sparse graphs | Dense graphs |
Practice Questions: Graph Representation
Test your understanding with these hands-on exercises.
Problem: Convert an edge list to an adjacency list representation.
// Input: n = 4, edges = [[0,1], [0,2], [1,2], [1,3]]
// Output: [[1,2], [0,2,3], [0,1], [1]]
public static List> buildAdjList(int n, int[][] edges) {
// Your code here
} Show Solution
public static List> buildAdjList(int n, int[][] edges) {
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]); // Undirected
}
return adj;
} Problem: Convert an adjacency list to an adjacency matrix.
// Input: adj = [[1,2], [0,2], [0,1]]
// Output: [[0,1,1], [1,0,1], [1,1,0]]
public static int[][] listToMatrix(List> adj) {
// Your code here
} Show Solution
public static int[][] listToMatrix(List> adj) {
int n = adj.size();
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int neighbor : adj.get(i)) {
matrix[i][neighbor] = 1;
}
}
return matrix;
} Problem: Build a weighted graph using HashMap where vertices can be any integer (not necessarily 0 to n-1).
// Input: edges = [[100,200,5], [200,300,10], [100,300,15]]
// (format: [from, to, weight])
// Output: HashMap with weighted adjacency list
public static Map> buildWeightedGraph(int[][] edges) {
// Your code here
} Show Solution
public static Map> buildWeightedGraph(int[][] edges) {
Map> graph = new HashMap<>();
for (int[] edge : edges) {
int from = edge[0], to = edge[1], weight = edge[2];
graph.computeIfAbsent(from, k -> new ArrayList<>())
.add(new int[]{to, weight});
graph.computeIfAbsent(to, k -> new ArrayList<>())
.add(new int[]{from, weight}); // Undirected
}
return graph;
}
// Access: graph.get(100) returns [[200,5], [300,15]] DFS (Depth-First Search)
What is Depth-First Search (DFS)?
Depth-First Search (DFS) is a graph traversal algorithm that explores as deep as possible along each branch before backtracking. Starting from a source node, DFS goes to a neighbor, then to that neighbor's neighbor, and keeps going deeper until it hits a dead end (a node with no unvisited neighbors). Only then does it backtrack to explore other paths. It uses a Stack data structure - either implicitly through recursion's call stack, or explicitly with a Stack object.
Think of DFS like exploring a maze: you pick a path and keep walking until you hit a wall, then go back to the last intersection and try a different path. This "go deep first" strategy makes DFS perfect for finding paths, detecting cycles, topological sorting, solving puzzles, and exploring all possibilities. Time Complexity: O(V + E) where V = vertices and E = edges.
Uses Stack (LIFO)
Last In, First Out structure. The most recently discovered node is explored first. Recursion automatically uses the call stack, so DFS is naturally recursive!
Go Deep First
When you find a neighbor, immediately explore it before looking at other neighbors. It's like following one complete path in a maze before trying alternatives.
Backtracking
When you hit a dead end (no unvisited neighbors), go back to the previous node and try other paths. This is how DFS eventually explores the entire graph.
Real-World Analogy
Imagine you're in a library looking for a specific book. DFS approach: Pick an aisle, walk to the very end checking each shelf, then backtrack and try the next aisle. You fully explore one path before starting another. This is efficient when the book might be anywhere and you need to search thoroughly!
Recursive DFS (Most Common)
void dfs(int start) {
boolean[] visited = new boolean[adj.size()];
dfsHelper(start, visited);
}
void dfsHelper(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsHelper(neighbor, visited);
}
}
}Understanding Recursive DFS
The dfs(start) method initializes a visited array to track which nodes we've seen, then calls the helper. In dfsHelper(node, visited), we first mark the current node as visited (so we don't revisit it later), then process it (here we just print, but you might collect data or check conditions). Next, we loop through all neighbors of this node, and for each unvisited neighbor, we recursively call dfsHelper on it.
Why "depth-first"? When we find an unvisited neighbor, we immediately dive into it (go deeper) before checking other neighbors. It's like exploring a maze by always taking the first path until you hit a dead end, then backtracking!
Iterative DFS with Explicit Stack
void dfsIterative(int start) {
boolean[] visited = new boolean[adj.size()];
Stack stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
visited[node] = true;
System.out.print(node + " ");
// Add neighbors in reverse for same order as recursive
List neighbors = adj.get(node);
for (int i = neighbors.size() - 1; i >= 0; i--) {
if (!visited[neighbors.get(i)]) {
stack.push(neighbors.get(i));
}
}
}
}
} Why use iterative instead of recursive?
Each recursive call uses memory on the "call stack", and very deep graphs can cause StackOverflowError! The solution is to use our own Stack data structure instead of relying on recursion. The algorithm works by pushing the starting node onto the stack, then repeatedly popping a node, marking it visited, processing it, and pushing all its unvisited neighbors onto the stack until the stack is empty. We add neighbors backwards (reverse order) so they come out in the same order as recursive DFS.
When to use: Very deep graphs (like a long chain of 10,000 nodes) or when you need explicit control over the traversal stack.
DFS on 2D Grid (Island Problems)
void dfsGrid(char[][] grid, int r, int c, boolean[][] visited) {
int rows = grid.length, cols = grid[0].length;
// Boundary and visited check
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c]) {
return;
}
visited[r][c] = true;
// 4 directions: up, down, left, right
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] dir : dirs) {
dfsGrid(grid, r + dir[0], c + dir[1], visited);
}
}Grid DFS - A Very Common Pattern!
A 2D grid IS a graph! Each cell is a node, and adjacent cells (up/down/left/right) are its neighbors. The boundary check r < 0 || r >= rows || c < 0 || c >= cols prevents going off the grid. The directions array {{-1,0}, {1,0}, {0,-1}, {0,1}} represents: (-1,0) = up (row decreases), (1,0) = down (row increases), (0,-1) = left (column decreases), and (0,1) = right (column increases). For 8-directional movement including diagonals, add: {-1,-1}, {-1,1}, {1,-1}, {1,1}.
Common problems using this pattern: Number of Islands, Flood Fill, Surrounded Regions, Shortest Path in Binary Matrix.
Practice Questions: DFS Traversal
Test your understanding with these hands-on exercises.
Problem: Given a graph and a starting node, return all nodes reachable from the start using DFS.
// Input: adj = [[1,2], [0,3], [0], [1]], start = 0
// Output: [0, 1, 2, 3] (all nodes reachable from 0)
public static List findReachable(List> adj, int start) {
// Your code here
} Show Solution
public static List findReachable(List> adj, int start) {
List result = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
dfs(start, adj, visited, result);
return result;
}
private static void dfs(int node, List> adj,
boolean[] visited, List result) {
visited[node] = true;
result.add(node);
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited, result);
}
}
} Problem: Use DFS to find if a path exists between source and destination. Return the path if it exists.
// Input: adj = [[1,2], [0,3], [0,3], [1,2]], src = 0, dest = 3
// Output: [0, 1, 3] or [0, 2, 3] (any valid path)
public static List findPath(List> adj, int src, int dest) {
// Your code here
} Show Solution
public static List findPath(List> adj, int src, int dest) {
List path = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
if (dfsPath(src, dest, adj, visited, path)) {
return path;
}
return new ArrayList<>(); // No path found
}
private static boolean dfsPath(int node, int dest, List> adj,
boolean[] visited, List path) {
visited[node] = true;
path.add(node);
if (node == dest) return true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (dfsPath(neighbor, dest, adj, visited, path)) {
return true;
}
}
}
path.remove(path.size() - 1); // Backtrack
return false;
} Problem: Find ALL possible paths from source to destination (no repeated vertices).
// Input: adj = [[1,2], [0,2,3], [0,1,3], [1,2]], src = 0, dest = 3
// Output: [[0,1,3], [0,1,2,3], [0,2,3], [0,2,1,3]]
public static List> findAllPaths(List> adj, int src, int dest) {
// Your code here
} Show Solution
public static List> findAllPaths(List> adj, int src, int dest) {
List> result = new ArrayList<>();
List path = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
dfsAllPaths(src, dest, adj, visited, path, result);
return result;
}
private static void dfsAllPaths(int node, int dest, List> adj,
boolean[] visited, List path,
List> result) {
visited[node] = true;
path.add(node);
if (node == dest) {
result.add(new ArrayList<>(path)); // Found a path!
} else {
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsAllPaths(neighbor, dest, adj, visited, path, result);
}
}
}
// Backtrack to explore other paths
path.remove(path.size() - 1);
visited[node] = false;
} BFS (Breadth-First Search)
What is Breadth-First Search (BFS)?
Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors at the current depth level before moving to nodes at the next depth level. Starting from a source node, BFS first visits all nodes 1 step away, then all nodes 2 steps away, and so on - spreading outward like ripples in water. It uses a Queue data structure (FIFO - First In, First Out) to process nodes in the order they were discovered.
BFS is the go-to algorithm for finding the shortest path in unweighted graphs because it explores nodes level-by-level, guaranteeing that the first time you reach any node, you've found the shortest path to it! Think of it like ripples spreading in water when you drop a stone - they expand equally in all directions. Time Complexity: O(V + E) where V = vertices and E = edges.
Uses Queue (FIFO)
First In, First Out structure. Nodes discovered first are explored first. This ensures we process all nodes at distance 1 before any at distance 2, and so on.
Level-by-Level
BFS explores nodes in "waves" - first all neighbors (level 1), then all neighbors' neighbors (level 2), etc. Like counting degrees of separation in social networks!
Shortest Path
In unweighted graphs, BFS guarantees the shortest path! Since it explores level-by-level, the first time you reach the destination is via the minimum number of edges.
Real-World Analogy
Imagine you're looking for a friend at a party. BFS approach: First ask everyone in your immediate circle (distance 1), then ask everyone they know (distance 2), etc. You spread your search equally in all directions rather than following one chain of people. This is perfect when you want to find someone with the fewest introductions!
Basic BFS Implementation
void bfs(int start) {
boolean[] visited = new boolean[adj.size()];
Queue queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true; // Mark BEFORE adding to queue!
queue.offer(neighbor);
}
}
}
} Understanding BFS
First, we create a visited array and a queue, mark the start node as visited, and add it to the queue. In the main loop, while the queue is not empty, we poll (remove from front) the next node and process it. Then we explore all neighbors of the current node - for each unvisited neighbor, we mark it visited AND add it to the queue.
BFS with Level Tracking
List> bfsLevels(int start) {
List> levels = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
Queue queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int size = queue.size(); // Nodes at current level
List level = new ArrayList<>();
for (int i = 0; i < size; i++) {
int node = queue.poll();
level.add(node);
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
levels.add(level);
}
return levels;
} The "Level-by-Level" Trick
The key insight is that int size = queue.size() captures how many nodes are at the CURRENT level. This works because at the start of each iteration, the queue contains ONLY nodes at the current distance from the source. The inner for-loop then processes exactly 'size' nodes (the current level) and adds their neighbors (which form the next level). After the loop completes, the queue contains only next-level nodes, ready for the next iteration.
Use cases: Tree level-order traversal, finding shortest distance, processing graph in layers (like social network "degrees of separation").
Shortest Path (Unweighted Graph)
int shortestPath(int start, int end) {
if (start == end) return 0;
boolean[] visited = new boolean[adj.size()];
Queue queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
distance++; // Moving to next level = +1 distance
for (int i = 0; i < size; i++) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (neighbor == end) return distance; // Found!
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
return -1; // No path exists
} Why BFS Finds Shortest Path
BFS explores level-by-level, visiting all nodes at distance 1 first, then all at distance 2, and so on. This means the first time we encounter the target node, we've found it via the shortest possible path! We track distance by incrementing it after processing each complete level. As soon as we find the 'end' node, we return immediately since we've found the shortest path. If the queue empties without finding the target, no path exists and we return -1.
Practice Questions: BFS Traversal
Test your understanding with these hands-on exercises.
Problem: Return nodes grouped by their level (distance from start).
// Input: adj = [[1,2], [0,3], [0,3], [1,2]], start = 0
// Output: [[0], [1,2], [3]] (level 0, level 1, level 2)
public static List> bfsLevels(List> adj, int start) {
// Your code here
} Show Solution
public static List> bfsLevels(List> adj, int start) {
List> levels = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
Queue queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int size = queue.size();
List level = new ArrayList<>();
for (int i = 0; i < size; i++) {
int node = queue.poll();
level.add(node);
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
levels.add(level);
}
return levels;
} Problem: Find the shortest path between two nodes and return the actual path (not just distance).
// Input: adj = [[1,2], [0,3], [0,3], [1,2]], src = 0, dest = 3
// Output: [0, 1, 3] (shortest path)
public static List shortestPath(List> adj, int src, int dest) {
// Your code here
} Show Solution
public static List shortestPath(List> adj, int src, int dest) {
int n = adj.size();
boolean[] visited = new boolean[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
Queue queue = new LinkedList<>();
visited[src] = true;
queue.offer(src);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == dest) break;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
parent[neighbor] = node;
queue.offer(neighbor);
}
}
}
// Reconstruct path
List path = new ArrayList<>();
if (!visited[dest]) return path; // No path
for (int node = dest; node != -1; node = parent[node]) {
path.add(0, node);
}
return path;
} Problem: Transform beginWord to endWord, changing one letter at a time. Each intermediate word must be in wordList. Return minimum transformations.
// Input: beginWord = "hit", endWord = "cog",
// wordList = ["hot","dot","dog","lot","log","cog"]
// Output: 5 (hit -> hot -> dot -> dog -> cog)
public static int ladderLength(String beginWord, String endWord, List wordList) {
// Your code here - use BFS!
} Show Solution
public static int ladderLength(String beginWord, String endWord, List wordList) {
Set wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue queue = new LinkedList<>();
queue.offer(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
char[] chars = word.toCharArray();
for (int j = 0; j < chars.length; j++) {
char original = chars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[j] = c;
String newWord = new String(chars);
if (newWord.equals(endWord)) return level + 1;
if (wordSet.contains(newWord)) {
queue.offer(newWord);
wordSet.remove(newWord); // Mark visited
}
}
chars[j] = original;
}
}
level++;
}
return 0;
} Connected Components
What is a Connected Component?
A Connected Component is a maximal group of vertices in an undirected graph where there exists a path between every pair of vertices within that group. Think of it as an "island" of connected nodes - you can travel from any node to any other node within the same component, but you cannot reach nodes in other components without adding new edges. A graph can have one component (fully connected) or multiple components (disconnected graph).
Finding connected components is a fundamental graph operation used everywhere: social network analysis (finding friend groups that don't overlap), image processing (identifying separate objects in an image), network reliability (detecting isolated segments), and recommendation systems (grouping similar items). The algorithm is simple: keep running DFS/BFS from unvisited nodes until everyone is visited!
Single Component
All nodes are reachable from any other node - the entire graph is connected. Think: a fully connected social network where everyone knows everyone through some chain of friends. One DFS from any node visits everyone!
Multiple Components
Graph has isolated groups with no path between them. Think: separate friend circles that don't overlap, or islands in an ocean. Each DFS from a new unvisited node discovers a new component!
Finding Algorithm
Use DFS/BFS from each unvisited node. Each complete traversal discovers one component. Count how many times you start a new traversal = number of components!
Count Connected Components
int countComponents(int n, int[][] edges) {
// Step 1: Build adjacency list
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
// Step 2: DFS from each unvisited node
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited); // Explore entire component
count++; // Found a new component!
}
}
return count;
} The Connected Components Algorithm
First, we build the graph by converting the edge list to adjacency list format. Then we loop through all vertices from 0 to n-1. Whenever we find an unvisited vertex, we've discovered a NEW component! We run DFS from this vertex, which marks ALL nodes in this component as visited, then increment our count. We continue the loop, skipping already-visited nodes and starting DFS only from unvisited ones.
Real-world analogy: Counting friend groups! Start with any person, mark everyone they can reach through friendships - that's one group. Find the next unvisited person and repeat.
DFS Helper for Components
void dfs(int node, List> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
} Simple but Powerful
This is the simplest form of DFS - just mark and explore. We mark the current node as visited with visited[node] = true, then for each unvisited neighbor, we recursively call DFS. When this function returns, ALL nodes reachable from 'node' are marked as visited. It's like a flood - once you pour water on one cell, it spreads to all connected cells.
Number of Islands (Classic Grid Problem)
int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
dfsIsland(grid, i, j); // Sink the island
count++; // Found a new island!
}
}
}
return count;
}Number of Islands - Interview Favorite!
In this problem, the grid contains '1' for land and '0' for water. An island is a group of '1's connected horizontally or vertically (not diagonally). The algorithm works by scanning the grid cell by cell using nested loops. When we find a '1' (land), we've discovered a new island, so we run DFS to "sink" the entire island by changing all connected '1's to '0's, then increment our island count. As we continue scanning, the sunken island won't be counted again because all its cells are now '0'.
Why "sink"? By changing '1' to '0', we mark it as visited without needing a separate visited array!
Island DFS (4-Directional)
void dfsIsland(char[][] grid, int r, int c) {
// Boundary check + water check
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
|| grid[r][c] != '1') {
return;
}
grid[r][c] = '0'; // Mark as visited (sink the land)
// Explore all 4 directions
dfsIsland(grid, r + 1, c); // down
dfsIsland(grid, r - 1, c); // up
dfsIsland(grid, r, c + 1); // right
dfsIsland(grid, r, c - 1); // left
}The "Flood Fill" Pattern
The base case handles three stopping conditions: r < 0 || r >= grid.length checks for vertical out-of-bounds, c < 0 || c >= grid[0].length checks for horizontal out-of-bounds, and grid[r][c] != '1' stops at water or already visited cells. We mark cells as visited by setting grid[r][c] = '0' (sinking the land), then explore all 4 directions by recursively calling DFS on up, down, left, and right cells. This approach saves O(rows x cols) space by modifying the input grid instead of using a separate visited array.
Note: If you can't modify the input, use visited[][] array or change '1' to '2' and restore later.
Practice Questions: Connected Components
Test your understanding with these hands-on exercises.
Problem: Given n nodes and edges, count the number of connected components.
// Input: n = 5, edges = [[0,1], [1,2], [3,4]]
// Output: 2 (components: {0,1,2} and {3,4})
public static int countComponents(int n, int[][] edges) {
// Your code here
}Show Solution
public static int countComponents(int n, int[][] edges) {
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited);
count++;
}
}
return count;
}
private static void dfs(int node, List> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) dfs(neighbor, adj, visited);
}
} Problem: Count the number of islands in a 2D grid ('1' = land, '0' = water).
// Input: grid = [['1','1','0','0'],
// ['1','1','0','0'],
// ['0','0','1','0'],
// ['0','0','0','1']]
// Output: 3
public static int numIslands(char[][] grid) {
// Your code here
}Show Solution
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
sinkIsland(grid, i, j);
count++;
}
}
}
return count;
}
private static void sinkIsland(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
|| grid[r][c] != '1') return;
grid[r][c] = '0'; // Sink the land
sinkIsland(grid, r + 1, c);
sinkIsland(grid, r - 1, c);
sinkIsland(grid, r, c + 1);
sinkIsland(grid, r, c - 1);
}Problem: Find the maximum area of an island in a 2D grid.
// Input: grid = [[0,0,1,0,0],
// [0,1,1,1,0],
// [0,0,1,0,0]]
// Output: 5 (the cross-shaped island)
public static int maxAreaOfIsland(int[][] grid) {
// Your code here
}Show Solution
public static int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, calculateArea(grid, i, j));
}
}
}
return maxArea;
}
private static int calculateArea(int[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
|| grid[r][c] != 1) return 0;
grid[r][c] = 0; // Mark visited
return 1 + calculateArea(grid, r + 1, c)
+ calculateArea(grid, r - 1, c)
+ calculateArea(grid, r, c + 1)
+ calculateArea(grid, r, c - 1);
}Cycle Detection
What is a Cycle in a Graph?
A cycle is a path in a graph that starts and ends at the same vertex, passing through at least one edge without repeating any edge. In simple terms, it's a "closed loop" where you can start at a node, travel through a series of edges, and return to where you started. Detecting cycles is crucial because many algorithms (like finding shortest paths or topological sorting) require graphs without cycles, and cycles can indicate problems like deadlocks or circular dependencies.
Cycle detection is essential across many domains: validating data structures (trees must be acyclic), deadlock detection in operating systems (processes waiting in a circle), dependency resolution (detecting circular imports/dependencies), course prerequisite validation (can't have A require B and B require A), and detecting infinite loops in workflows. The detection approach differs significantly between undirected and directed graphs!
Why Different Approaches?
In undirected graphs, every edge A-B is bidirectional (A→B and B→A). When traversing from A to B, we'll see A in B's neighbors - but that's NOT a cycle! We need to track the parent to distinguish between "came from here" vs "found a back edge." In directed graphs, edges are one-way, so we use a three-color system (White/Gray/Black) to detect if we're visiting a node that's still being processed.
Undirected Graph Cycles
Track the parent node during DFS. When we find a visited neighbor that is NOT our parent, we've found a cycle! The parent check prevents false positives from the bidirectional nature of undirected edges.
Example: A-B-C-A forms a cycle. Traversing A→B→C, when at C we see A is visited and A ≠ parent (B). Cycle detected!
Directed Graph Cycles
Use three-color marking: WHITE (unvisited), GRAY (currently in DFS stack), BLACK (completely done). If during exploration we encounter a GRAY node, we've found a back edge - that's a cycle!
Example: A→B→C→A. Processing A (gray)→B (gray)→C (gray). C sees A is GRAY = cycle!
Undirected Graph - Main Function
boolean hasCycleUndirected(int n, List> adj) {
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfsCycle(i, -1, adj, visited)) {
return true; // Cycle found!
}
}
}
return false; // No cycle
} The Setup for Cycle Detection
We need to check all vertices because the graph might be disconnected, meaning a cycle could exist in any component. The parent parameter starts as -1 because the starting node has no parent in the DFS tree. We use an early return strategy: as soon as we find a cycle, we return true immediately without checking the rest. If the loop completes without finding any cycles, we've checked every component and can safely return false.
Undirected Graph - DFS with Parent Tracking
boolean dfsCycle(int node, int parent, List> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (dfsCycle(neighbor, node, adj, visited)) {
return true;
}
} else if (neighbor != parent) {
// Visited neighbor that's NOT our parent = CYCLE!
return true;
}
}
return false;
} Why Track the Parent?
In undirected graphs, if node A connects to node B, then B also connects back to A. This creates a false positive risk: when we're at B (having come from A), we'll see A as a "visited neighbor" - but that's not actually a cycle! The solution is to track which node we came from (the parent) and ignore it when checking for cycles. The cycle detection logic is: if a neighbor is unvisited, we explore it normally with DFS. If a neighbor is visited AND it's our parent, we ignore it since that's just the edge we came from. But if a neighbor is visited AND it's NOT our parent, we've found a real cycle!
Example: A-B-C-A is a cycle. When at C, we see A is visited and A is not our parent (B is). Cycle detected!
Directed Graph - Three-Color Algorithm
// WHITE = 0 (unvisited), GRAY = 1 (in progress), BLACK = 2 (done)
boolean hasCycleDirected(int n, List> adj) {
int[] color = new int[n]; // All WHITE (0) initially
for (int i = 0; i < n; i++) {
if (color[i] == 0) { // WHITE - not visited
if (dfsCycleDirected(i, adj, color)) {
return true;
}
}
}
return false;
} Why Three Colors Instead of Two?
The problem with just visited/unvisited is that in directed graphs, visiting a node twice doesn't always indicate a cycle! For example, consider A->B->C and A->C. When exploring A->B->C, then A->C, we see C is already visited, but that's NOT a cycle! The solution is to use three states: WHITE (0) means we haven't visited the node yet, GRAY (1) means the node is currently being explored and is in our current DFS path, and BLACK (2) means the node is completely finished with all descendants visited. A cycle exists only when we find a GRAY node, which means we've encountered a node that's already in our current path!
Directed Graph - Color-Based DFS
boolean dfsCycleDirected(int node, List> adj, int[] color) {
color[node] = 1; // GRAY - currently being processed
for (int neighbor : adj.get(node)) {
if (color[neighbor] == 1) {
// Back edge to GRAY node = CYCLE!
return true;
}
if (color[neighbor] == 0) { // WHITE - unvisited
if (dfsCycleDirected(neighbor, adj, color)) {
return true;
}
}
// BLACK nodes are already done - skip them
}
color[node] = 2; // BLACK - completely processed
return false;
} The Three-Color Algorithm Step by Step
When we enter a node, we color it GRAY to indicate we're currently exploring it. Then we check each neighbor: if a neighbor is GRAY, we've found a node already in our current path, which means we have a cycle! If a neighbor is WHITE (unvisited), we explore it recursively. If a neighbor is BLACK (already fully explored), we skip it since it's safe and there's no cycle through this path. Once all neighbors are processed, we color the current node BLACK to mark it as fully explored, then return false to indicate no cycle was found through this node.
Think of it as: GRAY = "I'm still on this path". Finding another GRAY node means we've circled back to where we came from!
Understanding the Three-Color Algorithm
- WHITE (0): Node not yet visited
- GRAY (1): Node is currently in the DFS stack (being processed)
- BLACK (2): Node completely processed, all descendants visited
Finding a GRAY node while exploring means we've found a back edge → Cycle detected!
Practice Questions: Cycle Detection
Test your understanding with these hands-on exercises.
Problem: Detect if an undirected graph contains a cycle using DFS with parent tracking.
// Input: n = 4, edges = [[0,1], [1,2], [2,0], [2,3]]
// Output: true (cycle: 0 -> 1 -> 2 -> 0)
public static boolean hasCycle(int n, int[][] edges) {
// Your code here
}Show Solution
public static boolean hasCycle(int n, int[][] edges) {
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfsCycle(i, -1, adj, visited)) return true;
}
}
return false;
}
private static boolean dfsCycle(int node, int parent,
List> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (dfsCycle(neighbor, node, adj, visited)) return true;
} else if (neighbor != parent) {
return true; // Cycle found!
}
}
return false;
} Problem: Detect if a directed graph contains a cycle using the three-color algorithm.
// Input: n = 4, edges = [[0,1], [1,2], [2,0], [2,3]]
// Output: true (cycle: 0 -> 1 -> 2 -> 0)
public static boolean hasCycleDirected(int n, int[][] edges) {
// Your code here - use WHITE/GRAY/BLACK coloring
}Show Solution
public static boolean hasCycleDirected(int n, int[][] edges) {
List> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]); // Directed: only one direction
}
int[] color = new int[n]; // 0=WHITE, 1=GRAY, 2=BLACK
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
if (dfsCycleDirected(i, adj, color)) return true;
}
}
return false;
}
private static boolean dfsCycleDirected(int node, List> adj, int[] color) {
color[node] = 1; // GRAY - in progress
for (int neighbor : adj.get(node)) {
if (color[neighbor] == 1) return true; // Back edge = cycle!
if (color[neighbor] == 0) {
if (dfsCycleDirected(neighbor, adj, color)) return true;
}
}
color[node] = 2; // BLACK - done
return false;
} Problem: Given numCourses and prerequisites, determine if you can finish all courses. A prerequisite [a, b] means you must take course b before course a.
// Input: numCourses = 4, prerequisites = [[1,0], [2,1], [3,2], [1,3]]
// Output: false (cycle: 1 -> 2 -> 3 -> 1)
public static boolean canFinish(int numCourses, int[][] prerequisites) {
// Your code here - detect cycle in course dependency graph
}Show Solution
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
// Build graph: b -> a (must take b before a)
for (int[] prereq : prerequisites) {
adj.get(prereq[1]).add(prereq[0]);
}
int[] color = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (color[i] == 0) {
if (hasCycle(i, adj, color)) return false;
}
}
return true; // No cycle = can finish all courses
}
private static boolean hasCycle(int node, List> adj, int[] color) {
color[node] = 1; // GRAY
for (int neighbor : adj.get(node)) {
if (color[neighbor] == 1) return true;
if (color[neighbor] == 0 && hasCycle(neighbor, adj, color)) return true;
}
color[node] = 2; // BLACK
return false;
} Interactive Demos
Experiment with these interactive visualizations to deepen your understanding of graph traversals and representations.
Interactive: DFS vs BFS Traversal Comparison
Key Takeaways
Adjacency List is Preferred
Use adjacency list for most graphs - O(V + E) space, efficient for sparse graphs. Use matrix only when you need O(1) edge lookup.
DFS Uses Stack/Recursion
Depth-first explores as deep as possible before backtracking. Perfect for cycle detection, connected components, and path finding.
BFS Uses Queue
Breadth-first explores level-by-level like ripples in water. Guarantees shortest path in unweighted graphs - essential for distance problems!
Cycle Detection Differs
Undirected graphs: track parent to avoid false positives. Directed graphs: use three colors (WHITE/GRAY/BLACK) to detect back edges.
Grids are Graphs Too
2D grids are graphs where cells are nodes and adjacent cells are neighbors. Use 4-directional arrays for up/down/left/right movement.
Time Complexity: O(V + E)
Both DFS and BFS visit every vertex and edge once. This linear time makes them efficient for exploring entire graphs.
Knowledge Check
Which data structure does BFS use?
What is the space complexity of adjacency list for a graph with V vertices and E edges?
Which algorithm finds shortest path in unweighted graph?
In cycle detection for directed graphs, what does a GRAY node indicate?
What is the time complexity of BFS and DFS traversals?
When is adjacency matrix preferred over adjacency list?