Graphs | DSA Prep

Core Concepts

Graph Representation: Adjacency List (most common) or Adjacency Matrix.
Traversal (BFS & DFS): Crucial to track `visited` nodes to prevent infinite loops.
Topological Sort: Used for scheduling dependencies (e.g., course prerequisites).

graph LR A((0)) --- B((1)) A --- C((2)) B --- D((3)) C --- D D --- E((4)) classDef node fill:#e2e8f0,stroke:#94a3b8,color:#1e293b,font-weight:bold; class A,B,C,D,E node;

Cheatsheet Formulas

DFS Traversal: def dfs(node): if node in visited: return; visited.add(node); for neighbor in adj[node]: dfs(neighbor).
BFS Shortest Path: queue = [(start, 0)], visited.add(start). Pop (node, dist), if target return dist. Append unvisited neighbors with dist+1.
Topological Sort (Kahn's): Count in-degrees. Add nodes with in-degree 0 to queue. Pop, process, decrement neighbor in-degrees, if 0 add to queue.

Classic Problem: Number of Islands

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. (Solved here with DFS).

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0'; // mark visited
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
}

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
            
        def dfs(i, j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            grid[i][j] = '0' # mark visited
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
            
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        return count