Graphs, BFS, and DFS

Introduction

Graph algorithms are fundamental to computer science and software development. They help us solve problems involving relationships, connections, and paths between entities. Two of the most important graph traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

In this article, we’ll explore these concepts through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is a Graph?

A graph is a data structure consisting of:

• Vertices (Nodes): The entities in the graph
• Edges: The connections between vertices

Graphs can be:

• Directed: Edges have a direction (A → B)
• Undirected: Edges are bidirectional (A ↔ B)
• Weighted: Edges have associated values
• Unweighted: All edges are equal

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. Think of it as exploring a maze by always taking the first available path until you hit a dead end, then backtracking.

Key Characteristics:

• Uses a stack (or recursion) to track nodes
• Explores one path completely before moving to the next
• Memory efficient for deep graphs
• Perfect for finding connected components, paths, and cycles

When to Use DFS:

• Finding all connected components
• Pathfinding (when you need any path)
• Topological sorting
• Detecting cycles
• Solving puzzles and mazes

Breadth-First Search (BFS)

BFS explores all neighbors at the current depth level before moving to the next level. Think of it as exploring a tree level by level, or like ripples in water.

Key Characteristics:

• Uses a queue to track nodes
• Explores all nodes at distance d before nodes at distance d+1
• Guarantees finding the shortest path in unweighted graphs
• Requires more memory for wide graphs

When to Use BFS:

• Finding shortest paths in unweighted graphs
• Level-order traversal
• Finding minimum steps to reach a target
• Social network analysis (degrees of separation)

Problem 1: Number of Islands

Problem Statement

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

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Understanding the Problem

This is a classic connected components problem. Each island is a group of connected '1's. We need to:

1. Find all groups of connected '1's
2. Count how many such groups exist

Solution Strategy

We use DFS to “sink” (mark as visited) each island we encounter:

1. Iterate through every cell in the grid
2. When we find a '1' (land), we’ve found a new island
3. Use DFS to mark all connected land cells as visited (turn them to '0')
4. Count each successfully processed island

C# Solution

public class Solution 
{
    public int NumIslands(char[][] grid) 
    {
        int count = 0;
        
        // Iterate through every cell in the grid
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                // Count successfully processed islands
                count += Sink(grid, i, j);
            }
        }
        
        return count;
    }
    
    // DFS: Mark an entire island as visited by "sinking" it
    int Sink(char[][] grid, int i, int j)
    {
        // Base cases: Out of bounds or already visited/water
        if (i < 0 || j < 0 || 
            i >= grid.Length || 
            j >= grid[i].Length || 
            grid[i][j] == '0')
        {
            return 0; // Not an island or already processed
        }
        
        // Mark current cell as visited (sink it)
        grid[i][j] = '0';
        
        // Recursively sink all adjacent land cells
        Sink(grid, i + 1, j); // Right
        Sink(grid, i - 1, j); // Left
        Sink(grid, i, j + 1); // Down
        Sink(grid, i, j - 1); // Up
        
        // Return 1 to indicate we found and processed an island
        return 1;
    }
}

Python 3 Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                count += self.sink(grid, i, j)
        
        return count
    
    def sink(self, grid: List[List[str]], i: int, j: int) -> int:
        # Base cases: Out of bounds or already visited/water
        if (i < 0 or j < 0 or 
            i >= len(grid) or 
            j >= len(grid[i]) or 
            grid[i][j] == '0'):
            return 0
        
        # Mark current cell as visited
        grid[i][j] = '0'
        
        # Recursively sink all adjacent land cells
        self.sink(grid, i + 1, j)  # Right
        self.sink(grid, i - 1, j)  # Left
        self.sink(grid, i, j + 1)  # Down
        self.sink(grid, i, j - 1)  # Up
        
        return 1

Complexity Analysis

• Time Complexity: O(m × n) where m and n are the dimensions of the grid
• Space Complexity: O(m × n) in the worst case (when the entire grid is one island, recursion stack depth)

Problem 2: Max Area of Island

Problem Statement

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Understanding the Problem

Similar to the previous problem, but now we need to:

1. Find all islands (connected components)
2. Calculate the area (size) of each island
3. Return the maximum area found

Solution Strategy

We use DFS to explore each island and count its cells:

1. Iterate through every cell
2. When we find a 1, use DFS to explore the entire island
3. Count cells as we explore
4. Track the maximum area encountered

C# Solution

public class Solution 
{
    private int maxArea = 0;
    private int currentArea = 0;
    
    public int MaxAreaOfIsland(int[][] grid) 
    {
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                // Explore island starting at (i, j)
                Sink(grid, i, j);
                
                // Update maximum area found
                maxArea = Math.Max(maxArea, currentArea);
                
                // Reset current area for next potential island
                currentArea = 0;
            }
        }
        
        return maxArea;
    }
    
    // DFS: Explore island and count its area
    void Sink(int[][] grid, int i, int j)
    {
        // Base cases: Out of bounds or water/visited
        if (i < 0 || j < 0 || 
            i >= grid.Length || 
            j >= grid[i].Length || 
            grid[i][j] == 0)
        {
            return;
        }
        
        // Count this cell as part of current island
        if (grid[i][j] == 1)
        {
            currentArea++;
        }
        
        // Mark as visited
        grid[i][j] = 0;
        
        // Recursively explore adjacent cells
        Sink(grid, i + 1, j); // Right
        Sink(grid, i - 1, j); // Left
        Sink(grid, i, j + 1); // Down
        Sink(grid, i, j - 1); // Up
    }
}

Python 3 Solution

class Solution:
    def __init__(self):
        self.max_area = 0
        self.current_area = 0
    
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                self.sink(grid, i, j)
                self.max_area = max(self.max_area, self.current_area)
                self.current_area = 0
        
        return self.max_area
    
    def sink(self, grid: List[List[int]], i: int, j: int) -> None:
        # Base cases: Out of bounds or water/visited
        if (i < 0 or j < 0 or 
            i >= len(grid) or 
            j >= len(grid[i]) or 
            grid[i][j] == 0):
            return
        
        # Count this cell as part of current island
        if grid[i][j] == 1:
            self.current_area += 1
        
        # Mark as visited
        grid[i][j] = 0
        
        # Recursively explore adjacent cells
        self.sink(grid, i + 1, j)  # Right
        self.sink(grid, i - 1, j)  # Left
        self.sink(grid, i, j + 1)  # Down
        self.sink(grid, i, j - 1)  # Up

Complexity Analysis

• Time Complexity: O(m × n) – we visit each cell at most once
• Space Complexity: O(m × n) – recursion stack in worst case

Problem 3: Word Ladder

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter
• Every si for 1 <= i <= k is in wordList
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example

Input: beginWord = "hit", endWord = "cog", 
       wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is 
"hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.

Understanding the Problem

This is a shortest path problem in an implicit graph:

• Each word is a node
• Two words are connected if they differ by exactly one letter
• We need the shortest path from beginWord to endWord

Solution Strategy

We use BFS because:

1. BFS guarantees finding the shortest path in unweighted graphs
2. We explore level by level (one letter change at a time)
3. First time we reach endWord, we have the shortest path

Algorithm:

1. Create a set from wordList for O(1) lookup
2. Use a queue for BFS, starting with beginWord
3. For each word, try changing each position to every letter (a-z)
4. If the new word is in the wordList and equals endWord, return the step count
5. Otherwise, add it to the queue and remove from wordList (mark as visited)

C# Solution

public class Solution 
{
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) 
    {
        // Convert wordList to HashSet for O(1) lookup
        HashSet<string> wordSet = new HashSet<string>(wordList);
        
        // BFS queue: stores words to explore
        Queue<string> queue = new Queue<string>();
        queue.Enqueue(beginWord);
        
        int step = 0;
        
        while (queue.Count > 0)
        {
            int size = queue.Count;
            
            // Process all words at current level
            for (int k = 0; k < size; k++)
            {
                string word = queue.Dequeue();
                
                // Try changing each character position
                for (int i = 0; i < word.Length; i++)
                {
                    // Try every letter from 'a' to 'z'
                    for (char ch = 'a'; ch <= 'z'; ch++)
                    {
                        // Create new word by replacing character at position i
                        StringBuilder newWord = new StringBuilder(word);
                        newWord[i] = ch;
                        string newWordStr = newWord.ToString();
                        
                        // Check if new word exists in wordList
                        if (wordSet.Contains(newWordStr))
                        {
                            // Found the end word! Return step count
                            if (newWordStr == endWord)
                            {
                                return step + 1;
                            }
                            
                            // Mark as visited by removing from set
                            wordSet.Remove(newWordStr);
                            
                            // Add to queue for next level exploration
                            queue.Enqueue(newWordStr);
                        }
                    }
                }
            }
            
            // Move to next level
            step++;
        }
        
        // No path found
        return 0;
    }
}

Python 3 Solution

import collections
import string

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # Convert to set for O(1) lookup
        word_set = set(wordList)
        
        # BFS queue: stores (word, step_count) tuples
        queue = collections.deque([(beginWord, 1)])
        
        while queue:
            word, step = queue.popleft()
            
            # Found the target word
            if word == endWord:
                return step
            
            # Try changing each character position
            for i in range(len(word)):
                # Try every letter from 'a' to 'z'
                for ch in string.ascii_lowercase:
                    # Create new word by replacing character at position i
                    new_word = word[:i] + ch + word[i+1:]
                    
                    # Check if new word exists in wordList
                    if new_word in word_set:
                        # Mark as visited by removing from set
                        word_set.remove(new_word)
                        
                        # Add to queue for next level exploration
                        queue.append((new_word, step + 1))
        
        # No path found
        return 0

Complexity Analysis

• Time Complexity: O(N × M × 26) where:
  • N = length of wordList
  • M = length of each word
  • 26 = alphabet size
• Space Complexity: O(N) for the queue and wordSet

Key Takeaways

When to Use DFS:

• Finding connected components
• Exploring all paths
• Topological sorting
• Memory-efficient for deep graphs
• Backtracking problems

When to Use BFS:

• Finding shortest paths in unweighted graphs
• Level-order traversal
• Minimum steps problems
• Guaranteed shortest path needed

General Graph Problem Solving Tips:

1. Identify the graph structure: What are the nodes? What are the edges?
2. Choose the right algorithm: DFS for exploration, BFS for shortest paths
3. Track visited nodes: Prevent infinite loops and redundant processing
4. Optimize data structures: Use sets for O(1) lookups, queues for BFS, stacks for DFS
5. Handle edge cases: Empty inputs, disconnected graphs, cycles

Conclusion

Graph algorithms are powerful tools for solving complex problems. Understanding when and how to use DFS and BFS will help you tackle a wide variety of programming challenges. The key is recognizing the problem pattern and choosing the appropriate traversal strategy.

Practice these algorithms with different problems to build intuition. Remember:

• DFS = “Go deep, then backtrack”
• BFS = “Explore level by level”

Happy coding!