Graph Algorithms Masterclass

Comprehensive guide to essential graph algorithms with implementations, patterns, and interview strategies.

Interview-Ready Content

This guide covers all major graph algorithms asked in FAANG interviews, from basic traversals to advanced topics like MST and strongly connected components.

Algorithm Categories

Traversal Algorithms

BFS
DFS
BFS vs DFS
Bidirectional BFS

Shortest Path

Dijkstra's Algorithm
Bellman-Ford
Floyd-Warshall
A* Search

Grid Problems

Rotten Oranges
Number of Islands
Flood Fill
Pacific Atlantic Water Flow
Shortest Path in Binary Matrix

Path Finding

Word Ladder
Snakes and Ladders
Water Jug

Graph Properties

Check for Bipartite
Clone a Graph
Transitive Closure
Strongly Connected Components

Topological Sort

Kahn's Algorithm
DFS-based Topo Sort
Course Schedule
Alien Dictionary

Union-Find (Disjoint Set)

Union by Rank
Path Compression
Connected Components
Cycle Detection

Advanced Topics

Minimum Spanning Tree
Articulation Points
Bridges
Network Flow

Interview Success Tips

Algorithm Selection

BFS for shortest path in unweighted graphs
Dijkstra for weighted graphs with non-negative weights
Bellman-Ford when negative weights are present
DFS for cycle detection, topological sort, connectivity
Union-Find for dynamic connectivity and MST
Topological sort for dependency resolution

Optimization Techniques

Use visited set to avoid revisiting nodes (prevents infinite loops)
For BFS level tracking: process queue by levels using for loop
Path compression in Union-Find for O(α(n)) amortized time
Bidirectional BFS for faster shortest path in large graphs
Multi-source BFS when multiple starting points exist
Memoization with DFS to avoid recomputation

Common Mistakes to Avoid

Forgetting to mark nodes as visited (causes infinite loops)
Using DFS for shortest path problems (use BFS instead)
Not handling disconnected components
Incorrect cycle detection in directed vs undirected graphs
Not checking for empty graph or single node edge cases
Modifying input grid without copying (if immutability needed)

Time/Space Complexity

BFS/DFS: O(V + E) time, O(V) space
Dijkstra: O((V + E) log V) with heap
Bellman-Ford: O(V × E) time
Floyd-Warshall: O(V³) time, O(V²) space
Union-Find: O(α(n)) per operation with optimizations
Topological Sort: O(V + E) time

BFS vs DFS: Head-to-Head

Aspect	BFS	DFS
Data Structure	Queue (FIFO)	Stack/Recursion (LIFO)
Traversal Order	Level by level	Depth first, then backtrack
Shortest Path	✓ Yes (unweighted graphs)	✗ No guarantee
Space Complexity	O(V) worst case	O(V) for recursion stack
When to Use	Shortest path, level order, web crawling	Cycle detection, topological sort, path existence

Interactive Graph Visualization

Graph Algorithm Visualizer

Loading interactive visualization...

Core Algorithm Implementations

Advanced Topics

Strongly Connected Components (Kosaraju's)

Used for finding cycles in directed graphs, analyzing connectivity

def strongly_connected_components(graph, n):
    """
    Find all strongly connected components in directed graph
    """
    # Step 1: Do DFS and store finish times
    visited = set()
    stack = []
    
    def dfs1(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs1(neighbor)
        stack.append(node)
    
    for i in range(n):
        if i not in visited:
            dfs1(i)
    
    # Step 2: Create transpose graph
    transpose = defaultdict(list)
    for node in graph:
        for neighbor in graph[node]:
            transpose[neighbor].append(node)
    
    # Step 3: DFS on transpose in reverse finish time order
    visited.clear()
    sccs = []
    
    def dfs2(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in transpose[node]:
            if neighbor not in visited:
                dfs2(neighbor, component)
    
    while stack:
        node = stack.pop()
        if node not in visited:
            component = []
            dfs2(node, component)
            sccs.append(component)
    
    return sccs

Bellman-Ford Algorithm

Handles negative weights, detects negative cycles

def bellman_ford(edges, n, source):
    """
    Shortest path with negative weights
    Can detect negative cycles
    Time: O(V*E)
    """
    dist = [float('inf')] * n
    dist[source] = 0
    
    # Relax all edges V-1 times
    for _ in range(n - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # Check for negative cycles
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None  # Negative cycle exists
    
    return dist

# Cheaper Flights Within K Stops (LeetCode 787)
def findCheapestPrice(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0
    
    for i in range(k + 1):
        temp = prices.copy()
        
        for u, v, price in flights:
            if prices[u] != float('inf'):
                temp[v] = min(temp[v], prices[u] + price)
        
        prices = temp
    
    return -1 if prices[dst] == float('inf') else prices[dst]

Floyd-Warshall Algorithm

Best for dense graphs, all-pairs shortest paths

def floyd_warshall(graph, n):
    """
    All-pairs shortest path
    Time: O(V³), Space: O(V²)
    """
    # Initialize distance matrix
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for u in graph:
        for v, weight in graph[u]:
            dist[u][v] = weight
    
    # Try all intermediate vertices
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], 
                                dist[i][k] + dist[k][j])
    
    return dist

# Find the City (LeetCode 1334)
def findTheCity(n, edges, distanceThreshold):
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for u, v, w in edges:
        dist[u][v] = dist[v][u] = w
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], 
                                dist[i][k] + dist[k][j])
    
    # Find city with smallest number of reachable cities
    min_count = n
    result = 0
    
    for i in range(n):
        count = sum(1 for j in range(n) 
                   if i != j and dist[i][j] <= distanceThreshold)
        if count <= min_count:
            min_count = count
            result = i
    
    return result

Prim's Algorithm (MST)

Greedy algorithm for minimum spanning tree

import heapq

def prim_mst(n, edges):
    """
    Minimum Spanning Tree using Prim's
    Time: O(E log V) with heap
    """
    graph = defaultdict(list)
    for u, v, weight in edges:
        graph[u].append((v, weight))
        graph[v].append((u, weight))
    
    visited = set()
    # Start from node 0
    pq = [(0, 0, -1)]  # (weight, node, parent)
    mst_cost = 0
    mst_edges = []
    
    while pq and len(visited) < n:
        weight, node, parent = heapq.heappop(pq)
        
        if node in visited:
            continue
        
        visited.add(node)
        mst_cost += weight
        
        if parent != -1:
            mst_edges.append((parent, node, weight))
        
        for neighbor, edge_weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(pq, (edge_weight, neighbor, node))
    
    return mst_cost, mst_edges

# Min Cost to Connect All Points (LeetCode 1584)
def minCostConnectPoints(points):
    n = len(points)
    visited = set([0])
    pq = []
    
    # Add all edges from point 0
    for i in range(1, n):
        dist = abs(points[0][0] - points[i][0]) + abs(points[0][1] - points[i][1])
        heapq.heappush(pq, (dist, i))
    
    cost = 0
    
    while len(visited) < n:
        dist, point = heapq.heappop(pq)
        
        if point in visited:
            continue
        
        visited.add(point)
        cost += dist
        
        for i in range(n):
            if i not in visited:
                new_dist = abs(points[point][0] - points[i][0]) + abs(points[point][1] - points[i][1])
                heapq.heappush(pq, (new_dist, i))
    
    return cost

Problem-Solving Patterns

Grid BFS/DFS Pattern

Convert grid to graph, use BFS for shortest path, DFS for connected components

Applicable Problems:

Number of IslandsRotten OrangesFlood FillShortest Path in Binary Matrix

def grid_bfs(grid, start):
    rows, cols = len(grid), len(grid[0])
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    queue = deque([start])
    visited = set([start])
    
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and 
                (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc))

Level Order BFS Pattern

Track levels/distance by processing queue in batches

Applicable Problems:

Word LadderShortest transformationsMinimum steps problems

def level_order_bfs(start, target):
    queue = deque([start])
    visited = set([start])
    level = 0
    
    while queue:
        level += 1
        for _ in range(len(queue)):
            current = queue.popleft()
            if current == target:
                return level
            for neighbor in get_neighbors(current):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

DFS with Memoization

Cache results to avoid recomputation (DFS + DP)

Applicable Problems:

Longest Increasing PathWord SearchUnique Paths

def dfs_with_memo(node, memo):
    if node in memo:
        return memo[node]
    
    result = 0
    for neighbor in get_neighbors(node):
        result = max(result, dfs_with_memo(neighbor, memo) + 1)
    
    memo[node] = result
    return result

Multi-source BFS

Initialize queue with multiple sources, process simultaneously

Applicable Problems:

Rotten Oranges01 MatrixWalls and Gates

def multi_source_bfs(sources):
    queue = deque(sources)
    visited = set(sources)
    
    while queue:
        current = queue.popleft()
        for neighbor in get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Cycle Detection Pattern

Use colors or visited/recursion stack for cycle detection

Applicable Problems:

Course ScheduleDetect Cycle in Graph

# For directed graph
def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    
    def dfs(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True  # Back edge
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False
    
    return any(color[node] == WHITE and dfs(node) 
               for node in graph)

Topological Sort Pattern

Process nodes with no dependencies first

Applicable Problems:

Course ScheduleAlien DictionarySequence Reconstruction

def topo_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == n else []

Union-Find Pattern

Group elements and check connectivity efficiently

Applicable Problems:

Number of Connected ComponentsGraph Valid TreeRedundant Connection

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        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
        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

Shortest Path with Dijkstra

Find shortest paths in weighted graphs (non-negative weights)

Applicable Problems:

Network Delay TimePath with Maximum ProbabilityCheapest Flights

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    visited = set()
    
    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, weight in graph[node]:
            if d + weight < dist[neighbor]:
                dist[neighbor] = d + weight
                heapq.heappush(pq, (dist[neighbor], neighbor))
    
    return dist

Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Notes
BFS/DFS	O(V + E)	O(V)	Adjacency list representation
Dijkstra (Binary Heap)	O((V+E) log V)	O(V)	Non-negative weights only
Bellman-Ford	O(V × E)	O(V)	Handles negative weights
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest paths
Topological Sort	O(V + E)	O(V)	Kahn's or DFS-based
Union-Find (optimized)	O(α(n))	O(n)	Amortized per operation
Prim's MST	O(E log V)	O(V)	With binary heap
Kruskal's MST	O(E log E)	O(V)	Sort edges + Union-Find

Common Pitfalls & Solutions

Forgetting Visited Set

Not maintaining visited set causes infinite loops in graphs with cycles.

❌ No visited tracking
✅ visited.add(node) when enqueuing/processing

Using DFS for Shortest Path

DFS doesn't guarantee shortest path in unweighted graphs.

❌ DFS for shortest path
✅ BFS for unweighted, Dijkstra for weighted

Wrong Cycle Detection

Directed and undirected graphs need different cycle detection approaches.

Undirected: Check parent ≠ neighbor
Directed: Use WHITE-GRAY-BLACK colors

Dijkstra with Negative Weights

Dijkstra fails with negative edge weights.

❌ Dijkstra with negative weights
✅ Use Bellman-Ford instead

Multi-source BFS Optimization

Initialize queue with all sources for parallel processing.

queue = deque(all_sources)
visited = set(all_sources)

Level Tracking in BFS

Process nodes level by level for distance calculation.

while queue:
for _ in range(len(queue)):
# Process current level

Test Your Knowledge

Graph Algorithms Quiz

Question 1 of 10

Which algorithm would you use to find the shortest path in an unweighted graph?

Practice Problems by Category

Easy

Flood FillLC 733
Number of IslandsLC 200
Clone GraphLC 133
Find Center of StarLC 1791

Medium

Rotten OrangesLC 994
Course ScheduleLC 207
Network Delay TimeLC 743
Graph Valid TreeLC 261
Surrounded RegionsLC 130
Min Height TreesLC 310

Hard

Word LadderLC 127
Alien DictionaryLC 269
Cheapest Flights K StopsLC 787
Find CityLC 1334
Reconstruct ItineraryLC 332

Quick Reference

When to use BFS

Shortest path (unweighted)
Level order traversal
Finding closest nodes
Multi-source problems

When to use DFS

Cycle detection
Topological sort
Path existence
Connected components

Algorithm Selection

Dijkstra: Weighted, non-negative
Union-Find: Connectivity queries
Topo Sort: Dependency resolution
MST: Minimum cost connection

Algorithm Categories

Traversal Algorithms

Shortest Path

Grid Problems

Path Finding

Graph Properties

Topological Sort

Union-Find (Disjoint Set)

Advanced Topics

Interview Success Tips

Algorithm Selection

Optimization Techniques

Common Mistakes to Avoid

Time/Space Complexity

BFS vs DFS: Head-to-Head

Interactive Graph Visualization

Graph Algorithm Visualizer

Core Algorithm Implementations

pythonBFS Implementation

pythonDFS Implementation

pythonDijkstra's Algorithm

pythonTopological Sort (Kahn's Algorithm - BFS)

pythonTopological Sort (DFS-based)

pythonUnion-Find (Disjoint Set)

pythonNumber of Islands

pythonRotten Oranges

pythonWord Ladder

pythonCheck for Bipartite

pythonClone a Graph

pythonShortest Path in Binary Matrix

pythonSurrounded Regions (LeetCode 130)

pythonAlien Dictionary (LeetCode 269)

pythonMinimum Height Trees (LeetCode 310)

Advanced Topics

Strongly Connected Components (Kosaraju's)

Bellman-Ford Algorithm

Floyd-Warshall Algorithm

Prim's Algorithm (MST)

Problem-Solving Patterns

Grid BFS/DFS Pattern

Applicable Problems:

Level Order BFS Pattern

Applicable Problems:

DFS with Memoization

Applicable Problems:

Multi-source BFS

Applicable Problems:

Cycle Detection Pattern

Applicable Problems:

Topological Sort Pattern

Applicable Problems:

Union-Find Pattern

Applicable Problems:

Shortest Path with Dijkstra

Applicable Problems:

Complexity Analysis

Common Pitfalls & Solutions

Forgetting Visited Set

Using DFS for Shortest Path

Wrong Cycle Detection

Dijkstra with Negative Weights

Multi-source BFS Optimization

Level Tracking in BFS

Test Your Knowledge

Graph Algorithms Quiz

Practice Problems by Category

Easy

Medium

Hard

Quick Reference

When to use BFS

When to use DFS

Algorithm Selection