Module 7.1 ⏱ 45 min read ⚡ Graph Theory & Traversals

Graph Representations & Traversals

Master adjacency matrices, adjacency lists, Breadth-First Search (BFS), Depth-First Search (DFS), and cycle detection paradigms.

1. Adjacency Matrix vs. Adjacency List

A graph consists of a set of vertices (nodes) $V$ connected by a set of edges $E$. Depending on density and operational constraints, graphs are typically represented in code using one of two formats:

Adjacency Matrix: A $V \times V$ 2D boolean or integer array where matrix entry `matrix[i][j]` indicates an edge between vertex $i$ and vertex $j$. It provides $O(1)$ constant time edge lookups but demands $O(V^2)$ space complexity, making it inefficient for sparse graphs.

Adjacency List: An array or hash map of lists where each vertex stores a collection of its neighboring vertices. It optimizes space efficiency to $O(V + E)$ and is the preferred choice for sparse network structures.

2. Breadth-First Search (BFS) & Depth-First Search (DFS)

Systematic exploration of graph structures relies on two foundational traversal engines:

Breadth-First Search (BFS): Explores the graph level by level outward from a starting vertex using a Queue. BFS guarantees finding the shortest path in unweighted graphs.

Depth-First Search (DFS): Explores as deep as possible along each branch before backtracking, utilizing recursion or an explicit stack. DFS is essential for cycle detection, topological sorting, and finding connected components like the classic Number of Islands problem.

// C++ Solution: Number of Islands (DFS Approach)
#include <vector>

class Solution {
private:
    void dfs(std::vector<std::vector<char>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0'; // Mark visited
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }
};
            

# Python Solution: Number of Islands (DFS Approach)
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
                return
            grid[r][c] = '0'
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)
            
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count
            

// Java Solution: Number of Islands (DFS Approach)
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for tracking the Number of Islands and performing Cycle Detection in directed and undirected graphs.

Quick Check: Test Your Intuition

Which graph traversal strategy uses a Queue data structure to visit nodes level by level, making it ideal for finding shortest paths in unweighted graphs?