Graph Algorithms Complete Guide: BFS, DFS, Dijkstra, and Union-Find Explained

Graphs are everywhere — social networks, maps, course prerequisites, file systems, the internet itself. They're also one of the most common interview topics at product companies, and one of the most poorly prepared.

Most students learn BFS and DFS in theory but can't write them from scratch in an interview. This guide fixes that with implementations you can understand, internalise, and reproduce.

---

Graph Fundamentals

Representations

A graph is a set of nodes (vertices) connected by edges. You can represent it two ways:

Adjacency List (preferred for most problems):

# Undirected graph: 1-2, 1-3, 2-4
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
}

# Directed graph: 1→2, 1→3, 2→4
directed = {
    1: [2, 3],
    2: [4],
    3: [],
    4: []
}

Adjacency Matrix (for dense graphs or when O(1) edge lookup needed):

# 0-indexed, n=4 nodes
matrix = [
    [0, 1, 1, 0],  # node 0 connects to 1, 2
    [1, 0, 0, 1],  # node 1 connects to 0, 3
    [1, 0, 0, 0],  # node 2 connects to 0
    [0, 1, 0, 0]   # node 3 connects to 1
]

Which to use: Adjacency list for most LeetCode problems. Matrix when edges are given as a 2D grid.

Building a Graph from Edge List

from collections import defaultdict

def build_graph(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # remove this line for directed graphs
    return graph

---

Algorithm 1: Depth-First Search (DFS)

Use when: Exploring all paths, detecting cycles, topological sort, connected components.

Recursive DFS

def dfs(graph, node, visited):
    visited.add(node)
    print(node)  # or process node
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Usage
visited = set()
dfs(graph, start_node, visited)

Iterative DFS (avoids stack overflow for deep graphs)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
        
        visited.add(node)
        print(node)  # process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

DFS on a Grid (Number of Islands)

Grids are implicit graphs — each cell connects to its 4 neighbours.

def num_islands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '#'  # mark visited (in-place)
        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':
                dfs(r, c)
                count += 1
    
    return count

---

Algorithm 2: Breadth-First Search (BFS)

Use when: Shortest path in an unweighted graph, level-by-level processing, minimum steps problems.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        print(node)  # process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS for Shortest Path

def bfs_shortest_path(graph, start, end):
    if start == end:
        return 0
    
    visited = set([start])
    queue = deque([(start, 0)])  # (node, distance)
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # no path exists

Multi-Source BFS (Rotting Oranges)

When multiple starting points exist, add them all to the queue initially.

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    
    # Add all rotten oranges as starting points
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, minutes)
            elif grid[r][c] == 1:
                fresh += 1
    
    minutes = 0
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    while queue:
        r, c, mins = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2  # rot it
                fresh -= 1
                minutes = max(minutes, mins + 1)
                queue.append((nr, nc, mins + 1))
    
    return minutes if fresh == 0 else -1

---

Algorithm 3: Cycle Detection

In Undirected Graphs (DFS)

def has_cycle_undirected(graph, n):
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:  # back edge = cycle
                return True
        return False
    
    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

In Directed Graphs (3-color DFS)

For directed graphs, we need 3 states: unvisited (0), in-progress (1), done (2).

def has_cycle_directed(graph, n):
    # 0 = unvisited, 1 = in current path, 2 = fully processed
    color = [0] * n
    
    def dfs(node):
        color[node] = 1  # mark as in-progress
        
        for neighbor in graph[node]:
            if color[neighbor] == 1:   # back edge → cycle
                return True
            if color[neighbor] == 0:   # unvisited
                if dfs(neighbor):
                    return True
        
        color[node] = 2  # fully processed
        return False
    
    for node in range(n):
        if color[node] == 0:
            if dfs(node):
                return True
    return False

---

Algorithm 4: Topological Sort

Use when: Ordering tasks with dependencies (course prerequisites, build systems, task scheduling).

Only works on Directed Acyclic Graphs (DAGs).

Kahn's Algorithm (BFS-based)

from collections import deque

def topological_sort(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Start with courses that have no prerequisites
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If we couldn't process all nodes, there's a cycle
    return order if len(order) == n else []

Course Schedule II (LeetCode #210) is exactly this — return order if possible, [] if there's a cycle.

---

Algorithm 5: Dijkstra's Algorithm

Use when: Shortest path in a weighted graph with non-negative weights.

import heapq

def dijkstra(graph, start, n):
    # graph[u] = [(weight, v), ...]
    distances = [float('inf')] * n
    distances[start] = 0
    
    # Min-heap: (distance, node)
    heap = [(0, start)]
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        # Skip if we've found a shorter path already
        if dist > distances[node]:
            continue
        
        for weight, neighbor in graph[node]:
            new_dist = dist + weight
            
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return distances

# Usage
graph = defaultdict(list)
for u, v, w in edges:  # u→v with weight w
    graph[u].append((w, v))
    
distances = dijkstra(graph, source, num_nodes)

Why not BFS? BFS finds the path with fewest edges. Dijkstra finds the path with minimum total weight. They're the same only if all edges have equal weight.

Time complexity: O((V + E) log V) with a min-heap.

---

Algorithm 6: Union-Find (Disjoint Set Union)

Use when: Detecting connected components, cycle detection in undirected graphs, Kruskal's MST.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already in same component → cycle!
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

# Detect cycle in undirected graph
def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):  # already connected → adding this edge creates cycle
            return True
    return False

Why Union-Find over DFS for cycle detection? When you process edges one at a time (streaming), Union-Find is more natural. DFS requires the full graph.

---

Which Algorithm for Which Problem

| Problem Type | Algorithm | |---|---| | Connected components | DFS or BFS (count how many separate traversals needed) | | Shortest path, unweighted | BFS | | Shortest path, weighted | Dijkstra | | Cycle detection, undirected | Union-Find or DFS | | Cycle detection, directed | DFS (3-color) | | Topological order | Kahn's (BFS) or DFS post-order | | Minimum spanning tree | Kruskal's (Union-Find) or Prim's | | All pairs shortest paths | Floyd-Warshall (small graphs) |

---

Interview Patterns at Indian Companies

Most common at all levels:

• Number of Islands (DFS/BFS on grid)
• Course Schedule I & II (cycle detection + topological sort)
• Rotting Oranges (multi-source BFS)
• Clone Graph (DFS/BFS with hash map)
• Pacific Atlantic Water Flow (reverse BFS from borders)

At product companies (Swiggy, Razorpay, Freshworks):

• Network Delay Time (Dijkstra)
• Number of Connected Components (Union-Find)
• Graph Valid Tree (Union-Find cycle detection)

Hard problems (FAANG aspirants):

• Word Ladder (BFS on implicit graph)
• Alien Dictionary (topological sort on implicit graph)
• Swim in Rising Water (Dijkstra variant)

---

The Practice Plan

Week 1: Master DFS + BFS templates. Solve Number of Islands, Clone Graph, Rotting Oranges.

Week 2: Cycle detection + topological sort. Solve Course Schedule I & II.

Week 3: Dijkstra + Union-Find. Solve Network Delay Time, Number of Connected Components.

Week 4: Mixed practice. Solve 10 random graph problems without knowing which algorithm applies first — practice pattern recognition.

Start today: Filter Practice by "Graphs" and attempt the Easy problems. Implement BFS and DFS from memory — every single time, no copy-paste.