Master DSA: Graph Representations & Fundamental Applications (Flood Fill & Rotten Oranges)

Graphs are among the most versatile and widely used non-linear data structures in computer science. They model complex real-world networks—such as social connections, road maps, utility grids, and internet routing tables—by representing entities as nodes and the relationships between them as edges.

This guide covers the core classifications of graphs, details the two primary representation methods (Adjacency Matrix and Adjacency List), and walks through step-by-step solutions for two classic grid-based graph problems: Flood Fill and Rotten Oranges.

1. Why Do We Need Graphs? (The Core Mental Model)

In linear data structures like arrays, linked lists, stacks, and queues, elements are arranged sequentially. In hierarchical structures like trees, elements have strict parent-child relationships with a single root and no cycles.

However, real-world data is rarely strictly linear or hierarchical. Consider these scenarios:

• Social Networks (e.g., Facebook, LinkedIn): You are a node. Your friends are also nodes. A mutual friendship is an edge connecting you. There is no "root" person, and connections can form closed loops (cycles).
• Navigation Systems (e.g., Google Maps): Intersections and cities are nodes. The roads connecting them are edges. These edges have weights representing physical distances or travel times.
• Web Crawling: Web pages are nodes, and hyperlinks are directed edges pointing from one page to another.

Real-Life Analogy

Think of a graph as a airline flight network. Each airport is a Vertex (Node). Each direct flight between two airports is an Edge. If you can fly from Chicago to New York and back on the same route, the connection is undirected (or bidirectional). If a budget airline only offers a one-way flight from Austin to Boston, that connection is directed. The ticket price or flight duration represents the weight of that edge.

2. Classifying Graphs (Types of Graphs)

Graphs are classified based on the directionality, weight, and connectivity of their edges.

Undirected vs. Directed Graphs

• Undirected Graph: Edges have no direction. If there is an edge between node $U$ and node $V$, you can traverse from $U \to V$ and from $V \to U$.
  Structure & Concept Flow

  Copy DiagramCopy

  Node A <=========> Node B

   
• Directed Graph (Digraph): Edges have a specific direction. If an edge points from $U \to V$, you can only travel from $U$ to $V$, not vice versa (unless a separate reverse edge exists).
  Structure & Concept Flow

  Copy DiagramCopy

  Node A ----------> Node B

   

Weighted vs. Unweighted Graphs

• Weighted Graph: Each edge has an associated numerical value (cost, distance, time, capacity).
  Structure & Concept Flow

  Copy DiagramCopy

  Node A ----( Weight: 15 )----> Node B

   
• Unweighted Graph: All edges are treated equally; there are no values associated with the connections.

Cyclic vs. Acyclic Graphs

• Cyclic Graph: Contains at least one path that starts at a vertex and loops back to the same vertex.
• Acyclic Graph: Contains no cycles. A highly important subcategory is the DAG (Directed Acyclic Graph), which is heavily used in scheduling, dependency resolution, and git version control.

Summary of Graph Classifications

3. Graph Representation: Adjacency Matrix

An Adjacency Matrix is a 2D array of size $V \times V$, where $V$ is the number of vertices in the graph.

Mathematical Definition

For a graph $G = (V, E)$, the adjacency matrix $M$ is defined as:

• $M[i][j] = 1$ (or the edge weight) if there is an edge from vertex $i$ to vertex $j$.
• $M[i][j] = 0$ if there is no edge between vertex $i$ and vertex $j$.

Visualizing an Undirected Graph to Matrix

Consider a graph with 4 vertices ($0, 1, 2, 3$) and the following edges: $(0-1), (0-2), (1-2), (2-3)$.

The corresponding Adjacency Matrix is:

Note: For an undirected graph, the adjacency matrix is always symmetric along the main diagonal ($M[i][j] == M[j][i]$).

Java Implementation: Adjacency Matrix

public class AdjacencyMatrixGraph {
    private int[][] matrix;
    private int numVertices;

    public AdjacencyMatrixGraph(int numVertices) {
        this.numVertices = numVertices;
        this.matrix = new int[numVertices][numVertices];
    }

    // Add edge for an undirected graph
    public void addEdge(int source, int destination) {
        matrix[source][destination] = 1;
        matrix[destination][source] = 1; // Remove this line for a directed graph
    }

    // Print the matrix representation
    public void printGraph() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);

        graph.printGraph();
    }
}

Complexity Analysis

• Space Complexity: $O(V^2)$ — Regardless of how many edges exist, we must allocate a $V \times V$ grid.
• Time Complexity:
  • Add Edge: $O(1)$
  • Remove Edge: $O(1)$
  • Check Edge Existence ($U \to V$): $O(1)$
  • Find Neighbors of a Vertex: $O(V)$ (must scan an entire row)

4. Graph Representation: Adjacency List

An Adjacency List represents a graph as an array of linked lists, array lists, or vectors. The index of the array represents a vertex, and each element in the list at that index represents the neighbors of that vertex.

Visualizing an Undirected Graph to List

Using the same graph:

The Adjacency List representation:

Java Implementation: Adjacency List

import java.util.ArrayList;
import java.util.List;

public class AdjacencyListGraph {
    private List<List<Integer>> adjList;
    private int numVertices;

    public AdjacencyListGraph(int numVertices) {
        this.numVertices = numVertices;
        this.adjList = new ArrayList<>(numVertices);
        
        for (int i = 0; i < numVertices; i++) {
            this.adjList.add(new ArrayList<>());
        }
    }

    // Add edge for an undirected graph
    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); // Remove this line for a directed graph
    }

    // Print the list representation
    public void printGraph() {
        System.out.println("Adjacency List:");
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer neighbor : adjList.get(i)) {
                System.out.print(" -> " + neighbor);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyListGraph graph = new AdjacencyListGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);

        graph.printGraph();
    }
}

Complexity Analysis

• Space Complexity: $O(V + E)$ for directed graphs, $O(V + 2E)$ for undirected graphs. This is highly space-efficient for sparse graphs (graphs where $E \ll V^2$).
• Time Complexity:
  • Add Edge: $O(1)$ (appending to the end of a list)
  • Remove Edge: $O(V)$ in the worst case (searching the list to delete)
  • Check Edge Existence ($U \to V$): $O(\text{degree}(U))$ where degree is the number of neighbors of $U$.
  • Find Neighbors of a Vertex: $O(\text{degree}(U))$ (only iterate over actual neighbors)

5. Comparative Analysis: Matrix vs. List

6. Graph Traversal Foundations

To solve problems on graphs, we must visit their vertices systematically. The two fundamental traversal algorithms are:

Depth-First Search (DFS)

• Concept: Explores as deep as possible along each branch before backtracking.
• Data Structure: Uses a Stack (implicitly via recursion or explicitly).
• Analogy: Navigating a maze by walking down a path until you hit a dead end, then backtracking to the last intersection.

Breadth-First Search (BFS)

• Concept: Explores all neighbor nodes at the present depth level before moving to nodes at the next depth level.
• Data Structure: Uses a Queue (FIFO).
• Analogy: A ripple expanding outward when a stone is dropped into a pond.

7. Problem 1: Flood Fill (LeetCode 733)

Problem Statement

An image is represented by an $m \times n$ integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

1. Consider the starting pixel and any pixels connected 4-directionally to the starting pixel of the same color.
2. Change the color of all these pixels to the new color.
3. Repeat the process recursively for all newly colored pixels.

Real-Life Analogy

This is exactly how the Bucket Fill Tool works in drawing applications like MS Paint. When you click a region, the program changes the color of that pixel and spreads outward to all adjacent pixels of the same color, stopping only when it hits a boundary of a different color.

Step-by-Step Algorithm (DFS Approach)

1. Identify the starting color: originalColor = image[sr][sc].
2. If originalColor is already equal to the target color, return the image immediately to prevent an infinite loop.
3. Define a recursive helper function dfs(row, col):
   • Check boundary conditions: Ensure row and col are within grid limits.
   • Check color match: Ensure image[row][col] == originalColor.
   • If conditions are met, update image[row][col] = color.
   • Recursively call dfs on the 4-directional neighbors:
     • Up: dfs(row - 1, col)
     • Down: dfs(row + 1, col)
     • Left: dfs(row, col - 1)
     • Right: dfs(row, col + 1)

Visual Workflow

Java Implementation

public class FloodFillSolution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        
        // If the starting pixel already has the target color, no changes are needed
        if (originalColor != color) {
            dfs(image, sr, sc, originalColor, color);
        }
        
        return image;
    }

    private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
        // Boundary and base condition check
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != originalColor) {
            return;
        }

        // Update the color
        image[r][c] = newColor;

        // Recurse in 4 directions
        dfs(image, r - 1, c, originalColor, newColor); // Up
        dfs(image, r + 1, c, originalColor, newColor); // Down
        dfs(image, r, c - 1, originalColor, newColor); // Left
        dfs(image, r, c + 1, originalColor, newColor); // Right
    }
}

Complexity Analysis

• Time Complexity: $O(N \times M)$ where $N$ is the number of rows and $M$ is the number of columns. In the worst case, we visit every single pixel in the grid.
• Space Complexity: $O(N \times M)$ due to the recursion stack space in the worst-case scenario (e.g., a grid where all pixels have the same starting color).

8. Problem 2: Rotten Oranges (LeetCode 994)

Problem Statement

You are given an $m \times n$ grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Mental Model & Why BFS is Mandatory

This is a classic Multi-Source Shortest Path problem.

• Why not DFS? DFS explores deep along a single path. If we used DFS, one rotten orange would rot a long chain of oranges sequentially, giving an incorrect, inflated time count.
• Why BFS? BFS spreads outwards level-by-level (minute-by-minute). Since multiple oranges can rot simultaneously, we must start our BFS from all rotten oranges at the same time (multi-source).

Step-by-Step Algorithm

1. Initialization:
   • Create a Queue to store coordinates of rotten oranges: Queue<int[]>.
   • Initialize a counter freshCount = 0 to track remaining fresh oranges.
   • Scan the entire grid:
     • If grid[i][j] == 2, add its coordinates (i, j) to the queue.
     • If grid[i][j] == 1, increment freshCount.
2. Edge Case: If freshCount == 0, return 0 immediately (no fresh oranges to rot).
3. BFS Traversal (Level-by-Level):
   • Initialize minutes = 0.
   • Define direction arrays for easy 4-directional navigation: dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}.
   • While the queue is not empty and freshCount > 0:
     • Get the number of rotten oranges at the current level: size = queue.size().
     • Decrement/process all elements of this level:
       • Pop an orange (r, c) from the queue.
       • Check its 4 neighbors:
         • If a neighbor (nr, nc) is within bounds and is a fresh orange (grid[nr][nc] == 1):
           • Change it to rotten: grid[nr][nc] = 2.
           • Decrement freshCount.
           • Push (nr, nc) into the queue to rot its neighbors in the next minute.
     • If we successfully rotted any orange during this level, increment minutes.
4. Final Check: If freshCount == 0, return minutes; otherwise, return -1 (some fresh oranges are isolated and cannot be reached).

Visual Workflow

Java Implementation

import java.util.LinkedList;
import java.util.Queue;

public class RottenOrangesSolution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Step 1: Initialize queue with all rotten oranges and count fresh oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }
        
        // If there are no fresh oranges, 0 minutes are needed
        if (freshCount == 0) return 0;
        
        int minutes = 0;
        // Direction vectors for Up, Down, Left, Right
        int[] dRow = {-1, 1, 0, 0};
        int[] dCol = {0, 0, -1, 1};
        
        // Step 2: Multi-source BFS
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            boolean rottedThisMinute = false;
            
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];
                
                for (int d = 0; d < 4; d++) {
                    int nRow = r + dRow[d];
                    int nCol = c + dCol[d];
                    
                    // Check boundaries and if the orange is fresh
                    if (nRow >= 0 && nRow < rows && nCol >= 0 && nCol < cols && grid[nRow][nCol] == 1) {
                        grid[nRow][nCol] = 2; // Rot the orange
                        queue.offer(new int[]{nRow, nCol});
                        freshCount--;
                        rottedThisMinute = true;
                    }
                }
            }
            
            if (rottedThisMinute) {
                minutes++;
            }
        }
        
        // Step 3: If fresh oranges remain, return -1
        return freshCount == 0 ? minutes : -1;
    }
}

Complexity Analysis

• Time Complexity: $O(N \times M)$ where $N$ is the number of rows and $M$ is the number of columns. Every cell is scanned initially, and each cell is processed at most once during the BFS.
• Space Complexity: $O(N \times M)$ in the worst case. The queue can hold up to $N \times M$ elements if almost all oranges are rotten at the start.

9. Common Pitfalls & Debugging in Graph Algorithms

When writing graph traversals, minor mistakes can lead to infinite loops, stack overflows, or incorrect results. Keep these debugging strategies in mind:

1. The Infinite Loop (Missing Visited State)

• The Problem: In undirected graphs or cyclic directed graphs, traversing without tracking visited nodes causes the algorithm to bounce back and forth between adjacent nodes indefinitely.
• The Fix: Always use a boolean[] visited array (or a HashSet for non-integer nodes) to track visited nodes. In grid problems like Flood Fill, updating the cell's value directly to the target color can act as the "visited" state, but only if the target color is different from the original color.

2. Off-by-One Boundary Checks

• The Problem: Accessing grid[row][col] when row or col is out of bounds throws an ArrayIndexOutOfBoundsException.
• The Fix: Always perform boundary checks first in your conditional statements before accessing the grid values:
  JAVA

  Copy

  if (row < 0 || row >= maxRows || col < 0 || col >= maxCols || grid[row][col] == target)
  

3. Level-by-Level Processing in BFS

• The Problem: In problems like Rotten Oranges where you need to count "minutes" or "steps", failing to capture the queue size at the start of each level causes the step count to increment on every single node pop instead of once per level.
• The Fix: Always capture int size = queue.size() and use a nested loop to process exactly that many elements before incrementing your step/time counter.

Summary and Key Takeaways

• Graphs are non-linear data structures consisting of Vertices (nodes) and Edges (connections).
• Adjacency Matrices use $O(V^2)$ space and are ideal for dense graphs where edge lookups need to be $O(1)$.
• Adjacency Lists use $O(V + E)$ space and are highly efficient for sparse graphs and neighbor-iteration operations.
• Flood Fill is a classic connectivity problem that can be solved elegantly using Depth-First Search (DFS) by recursively spreading outward to matching neighbors.
• Rotten Oranges is a shortest-path/level-order problem that must be solved using Breadth-First Search (BFS).
• Multi-Source BFS is the go-to pattern when multiple starting points spread a state simultaneously across a network or grid.
• Boundary checks and visited states are the most critical safety guards in any graph traversal implementation to prevent stack overflows and infinite loops.