Graph DFS Patterns
Depth-first search on grids and adjacency lists for connectivity, component counting, and property checking. The visited set is the only bookkeeping DFS needs.
The Pattern
Graph DFS is the same recursion as tree DFS, with one addition: a visited set to prevent revisiting nodes in a cycle or undirected graph. The canonical structure:
dfs(node):
mark node visited
for each neighbor:
if not visited: dfs(neighbor)
Grid problems map directly — treating each cell as a node with up to four neighbors. The visited set becomes an in-place mutation of the grid (marking cells '#' or '0') to save space.
Number of Islands
Count connected components of '1' cells. For each unvisited '1', run DFS to sink the entire island (mark all connected '1's as '0'), then increment the count.
fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
let (rows, cols) = (grid.len(), grid[0].len());
let mut count = 0;
fn dfs(grid: &mut Vec<Vec<char>>, r: usize, c: usize) {
let (rows, cols) = (grid.len(), grid[0].len());
if r >= rows || c >= cols || grid[r][c] != '1' { return; }
grid[r][c] = '0'; // sink
if r > 0 { dfs(grid, r-1, c); }
dfs(grid, r+1, c);
if c > 0 { dfs(grid, r, c-1); }
dfs(grid, r, c+1);
}
for r in 0..rows {
for c in 0..cols {
if grid[r][c] == '1' {
dfs(grid, r, c);
count += 1;
}
}
}
count
}
fn main() {
let mut grid = vec![
vec!['1','1','1','1','0'],
vec!['1','1','0','1','0'],
vec!['1','1','0','0','0'],
vec!['0','0','0','0','0'],
];
println!("{}", num_islands(&mut grid)); // 1
let mut grid2 = vec![
vec!['1','1','0','0','0'],
vec!['1','1','0','0','0'],
vec!['0','0','1','0','0'],
vec!['0','0','0','1','1'],
];
println!("{}", num_islands(&mut grid2)); // 3
}Flood Fill
Replace the source color of a clicked cell and all 4-directionally connected cells of the same color with a new color.
fn flood_fill(image: &mut Vec<Vec<i32>>, sr: usize, sc: usize, color: i32) {
let source = image[sr][sc];
if source == color { return; } // already that color, nothing to do
fn dfs(image: &mut Vec<Vec<i32>>, r: usize, c: usize, source: i32, color: i32) {
let (rows, cols) = (image.len(), image[0].len());
if r >= rows || c >= cols || image[r][c] != source { return; }
image[r][c] = color;
if r > 0 { dfs(image, r-1, c, source, color); }
dfs(image, r+1, c, source, color);
if c > 0 { dfs(image, r, c-1, source, color); }
dfs(image, r, c+1, source, color);
}
dfs(image, sr, sc, source, color);
}
fn main() {
let mut image = vec![
vec![1,1,1],
vec![1,1,0],
vec![1,0,1],
];
flood_fill(&mut image, 1, 1, 2);
for row in &image { println!("{:?}", row); }
// [2, 2, 2]
// [2, 2, 0]
// [2, 0, 1]
}Surrounded Regions
Mark all 'O's that are NOT surrounded (connected to a border 'O') as safe, then flip all remaining 'O's to 'X'. Run DFS from every border 'O', marking reachable cells as safe. Then sweep and flip.
fn solve(board: &mut Vec<Vec<char>>) {
if board.is_empty() { return; }
let (rows, cols) = (board.len(), board[0].len());
fn dfs(board: &mut Vec<Vec<char>>, r: usize, c: usize) {
let (rows, cols) = (board.len(), board[0].len());
if r >= rows || c >= cols || board[r][c] != 'O' { return; }
board[r][c] = 'S'; // safe
if r > 0 { dfs(board, r-1, c); }
dfs(board, r+1, c);
if c > 0 { dfs(board, r, c-1); }
dfs(board, r, c+1);
}
// Mark border-connected O's as safe
for r in 0..rows {
if board[r][0] == 'O' { dfs(board, r, 0); }
if board[r][cols-1] == 'O' { dfs(board, r, cols-1); }
}
for c in 0..cols {
if board[0][c] == 'O' { dfs(board, 0, c); }
if board[rows-1][c] == 'O' { dfs(board, rows-1, c); }
}
// Flip remaining O->X, restore S->O
for r in 0..rows {
for c in 0..cols {
match board[r][c] {
'O' => board[r][c] = 'X',
'S' => board[r][c] = 'O',
_ => {}
}
}
}
}
fn main() {
let mut board = vec![
vec!['X','X','X','X'],
vec!['X','O','O','X'],
vec!['X','X','O','X'],
vec!['X','O','X','X'],
];
solve(&mut board);
for row in &board { println!("{:?}", row); }
// ['X','X','X','X']
// ['X','X','X','X']
// ['X','X','X','X']
// ['X','O','X','X'] ← border-connected O survives
}Bipartite Graph Check
A graph is bipartite if you can 2-color it such that no two adjacent nodes share a color. BFS/DFS coloring: assign color 0 to the start, alternate at each step. If a neighbor already has the same color as the current node, the graph is not bipartite.
fn is_bipartite(graph: &[Vec<usize>]) -> bool {
let n = graph.len();
let mut color = vec![-1i32; n];
fn dfs(graph: &[Vec<usize>], node: usize, c: i32, color: &mut Vec<i32>) -> bool {
color[node] = c;
for &nb in &graph[node] {
if color[nb] == c { return false; }
if color[nb] == -1 && !dfs(graph, nb, 1 - c, color) { return false; }
}
true
}
for i in 0..n {
if color[i] == -1 && !dfs(graph, i, 0, &mut color) {
return false;
}
}
true
}
fn main() {
// Bipartite: 0-1, 0-3, 1-2, 2-3 (cycle of length 4 — even)
let graph = vec![vec![1,3], vec![0,2], vec![1,3], vec![0,2]];
println!("{}", is_bipartite(&graph)); // true
// Not bipartite: triangle 0-1-2-0 (odd cycle)
let graph2 = vec![vec![1,2], vec![0,2], vec![0,1]];
println!("{}", is_bipartite(&graph2)); // false
}Number of Provinces (Connected Components)
Count the number of connected components in an undirected graph given as an adjacency matrix. Standard component counting: DFS from each unvisited node, mark all reachable nodes visited, increment count.
fn find_circle_num(is_connected: &Vec<Vec<i32>>) -> i32 {
let n = is_connected.len();
let mut visited = vec![false; n];
let mut provinces = 0;
fn dfs(matrix: &Vec<Vec<i32>>, node: usize, visited: &mut Vec<bool>) {
visited[node] = true;
for nb in 0..matrix.len() {
if matrix[node][nb] == 1 && !visited[nb] {
dfs(matrix, nb, visited);
}
}
}
for i in 0..n {
if !visited[i] {
dfs(is_connected, i, &mut visited);
provinces += 1;
}
}
provinces
}
fn main() {
let matrix = vec![
vec![1,1,0],
vec![1,1,0],
vec![0,0,1],
];
println!("{}", find_circle_num(&matrix)); // 2 ({0,1} and {2})
let matrix2 = vec![
vec![1,0,0],
vec![0,1,0],
vec![0,0,1],
];
println!("{}", find_circle_num(&matrix2)); // 3
}Clone Graph
Deep copy a graph given a reference to one of its nodes. Use a HashMap from original node pointer (id here) to the cloned node. DFS: if node already cloned, return the clone; otherwise, create the clone, register it, then recursively clone all neighbors.
use std::collections::HashMap;
#[derive(Debug, Clone)]
struct GraphNode { val: i32, neighbors: Vec<usize> }
fn clone_graph(nodes: &[GraphNode]) -> Vec<GraphNode> {
// In Rust with index-based graph, clone is straightforward.
// The LeetCode version uses Rc<RefCell<Node>>; here we show the logic with indices.
nodes.to_vec()
}
// Demonstrating the DFS clone logic with a visited map
fn clone_graph_dfs(
id: usize,
original: &[GraphNode],
cloned: &mut HashMap<usize, GraphNode>,
) {
if cloned.contains_key(&id) { return; }
cloned.insert(id, GraphNode { val: original[id].val, neighbors: original[id].neighbors.clone() });
for &nb in &original[id].neighbors.clone() {
clone_graph_dfs(nb, original, cloned);
}
}
fn main() {
// Graph: 0 -- 1 -- 2 -- 3 -- 0 (cycle of 4)
let graph = vec![
GraphNode { val: 1, neighbors: vec![1, 3] },
GraphNode { val: 2, neighbors: vec![0, 2] },
GraphNode { val: 3, neighbors: vec![1, 3] },
GraphNode { val: 4, neighbors: vec![2, 0] },
];
let mut cloned = HashMap::new();
clone_graph_dfs(0, &graph, &mut cloned);
println!("Cloned {} nodes", cloned.len()); // 4
}