Graph Representations and Traversals (DFS/BFS)

Core Concepts of Graphs

• Directed vs. Undirected: Whether edges have a specific start-to-end direction.
• Weighted vs. Unweighted: Whether edges carry values (costs/weights).
• Degree: The number of edges connected to a node. In directed graphs, this is split into In-degree (incoming) and Out-degree (outgoing).

Storing a Graph

Adjacency List

The most common way to represent a graph, mapping each node to a list of its immediate neighbors.

// n nodes (indexed 0 to n-1)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

// Add edge u → v
graph.get(u).add(v);

// For undirected graphs, also add v → u:
// graph.get(v).add(u);

Complexity: O(V + E) space. Ideal for sparse graphs (where $E \ll V^2$).

Adjacency Matrix

A 2D array where grid[u][v] indicates an edge from u to v.

int[][] matrix = new int[n][n];
matrix[u][v] = 1; // Or the edge weight w

Complexity: O(V²) space. Faster for checking if a specific edge exists (O(1)) and suitable for dense graphs.

Depth-First Search (DFS)

DFS explores as deeply as possible along a branch before backtracking.

boolean[] visited;

void dfs(List<List<Integer>> graph, int node) {
    visited[node] = true;
    process(node); // Execute business logic
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor);
        }
    }
}

// Handler for potentially disconnected components
void dfsAll(List<List<Integer>> graph, int n) {
    visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, i);
        }
    }
}

Complexity: O(V + E) time, O(V) space (recursive stack + visited array).

DFS Application: Number of Islands (LeetCode 200)

int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;
                sinkIsland(grid, r, c); // DFS to sink all connected land
            }
        }
    }
    return count;
}

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'; // Mark as visited
    sinkIsland(grid, r + 1, c);
    sinkIsland(grid, r - 1, c);
    sinkIsland(grid, r, c + 1);
    sinkIsland(grid, r, c - 1);
}

Breadth-First Search (BFS)

BFS explores layer-by-layer: visiting all immediate neighbors before moving to their children.

int bfs(List<List<Integer>> graph, int start, int target) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    
    queue.offer(start);
    visited[start] = true;
    int layerCount = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) { // Process one full layer
            int node = queue.poll();
            if (node == target) return layerCount;
            
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        layerCount++;
    }
    return -1; // Target not reachable
}

BFS for Shortest Path: In unweighted graphs, BFS is guaranteed to find the shortest path from source to target first. The layer number of the first visit to the target is the path length.

Clone Graph (LeetCode 133)

Create a deep copy of a graph. Use a HashMap to map original -> clone to manage cycles and ensure each node is cloned only once.

Map<Node, Node> clones = new HashMap<>();

Node cloneGraph(Node node) {
    if (node == null) return null;
    if (clones.containsKey(node)) return clones.get(node);
    
    Node clone = new Node(node.val);
    clones.put(node, clone);
    
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(cloneGraph(neighbor));
    }
    return clone;
}

Connected Components

Concept: A maximal set of nodes where a path exists between any two nodes.
To count components, iterate through all nodes; every time you find an unvisited node, trigger a DFS/BFS and increment the counter.

int countComponents(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    // ... initialize adjacency list ...
    
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(adj, visited, i);
            count++;
        }
    }
    return count;
}

Selection Guide: DFS vs. BFS

Cycle Detection in Directed Graphs

Using Three-Color Marking:

• White (0): Not visited.
• Gray (1): Currently being explored (on the recursion stack).
• Black (2): Fully explored (finished).

A cycle exists if we encounter a Gray node during a DFS.

int[] color; // 0, 1, or 2
boolean hasCycle = false;

void detectCycle(List<List<Integer>> activeGraph, int node) {
    color[node] = 1; // Mark as Gray (Processing)
    for (int neighbor : activeGraph.get(node)) {
        if (color[neighbor] == 1) {
            hasCycle = true;
            return;
        }
        if (color[neighbor] == 0) {
            detectCycle(activeGraph, neighbor);
        }
    }
    color[node] = 2; // Mark as Black (Finished)
}

Summary

• Adjacency Lists are the industry standard for most graph problems.
• DFS is elegant for exploring connectivity and deep paths; always use a visited set to avoid infinite cycles.
• BFS is the go-to algorithm for finding the "minimum number of steps" or layers.
• Always check if the input graph can have multiple disjoint components.