Graph Algorithms for Coding Interviews: BFS, DFS, Dijkstra & More

TL;DR

• Choose a graph algorithm from the required output and the graph constraints: direction, weights, connectivity and cycles.
• Use BFS for unweighted shortest paths, Dijkstra for nonnegative weights, Bellman–Ford for negative weights, and Floyd–Warshall for all-pairs distances when the graph is small enough.
• Topological ordering requires a directed acyclic graph. Union-find supports connectivity; Kruskal and Prim solve minimum-spanning-tree problems, not shortest paths.
• Test disconnected components, unreachable targets, cycles and boundary inputs. Explain the invariant as well as the complexity of the code you actually write.

Introduction

Graphs model dependencies, routes, connections and transitions between states. This guide explains the main algorithms, gives Python examples and shows how a change in the problem statement changes the solution. The exercises are study material, not a claim about how often a particular employer asks graph questions.

Table of Contents

• Graph Fundamentals
• Graph Representations
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Topological Sort
• Shortest Path: Dijkstra's Algorithm
• Shortest Path: Bellman-Ford Algorithm
• Minimum Spanning Tree: Kruskal's Algorithm
• Minimum Spanning Tree: Prim's Algorithm
• Cycle Detection
• Union-Find (Disjoint Set Union)
• Common Interview Patterns
• Practice Strategy
• Conclusion

Graph Fundamentals

Before diving into algorithms, make sure you have a solid understanding of graph terminology.

A graph consists of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Graphs can be:

• Directed or undirected: In a directed graph, edges have a direction (A to B is different from B to A). In an undirected graph, edges are bidirectional.
• Weighted or unweighted: In a weighted graph, each edge has a numerical cost or distance. In an unweighted graph, all edges are treated equally.
• Cyclic or acyclic: A cyclic graph contains at least one cycle (a path that starts and ends at the same vertex). A Directed Acyclic Graph (DAG) is a directed graph with no cycles and is especially important for dependency problems.
• Connected or disconnected: In an undirected graph, a connected graph has a path between every pair of vertices. A directed graph is strongly connected if there is a path from every vertex to every other vertex.

Understanding these properties helps you select the right algorithm for each problem.

Inputs and edge cases for these examples

The adjacency-list examples assume a finite graph with an entry for every vertex, including isolated vertices and vertices with no outgoing edges. Build missing empty lists before running a traversal, and pass a start vertex that exists. The edge-list builder discovers only vertices present in edges; add isolated vertices explicitly. Grid examples expect a rectangular grid. Recursion-based examples can reach Python’s recursion limit on long chains; use an iterative traversal when the input can be deep.

Undirected cycle detection below assumes a simple graph; parallel edges require tracking the identity of the incoming edge. Weighted examples use finite numeric weights. Dijkstra rejects negative weights. Kruskal returns a forest for a disconnected graph, while Prim returns only the start component; neither result proves that all vertices are connected. Kahn’s num_vertices must equal the number of graph keys. The bounded-stop example counts intermediate stops, so K stops allow K + 1 edges and -1 represents an unreachable target under its nonnegative-fare use case.

Graph Representations

There are two primary ways to represent a graph in code. Choosing the right representation affects both the clarity and performance of your solution.

Adjacency List

The adjacency list represents each vertex as a key in a dictionary (or array), with the value being a list of its neighbors. This is the most common representation in interviews.

# Unweighted directed graph
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': ['E'],
    'E': []
}

# Weighted directed graph
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3)],
    'C': [('D', 1), ('E', 5)],
    'D': [('E', 2)],
    'E': []
}

# Building from an edge list (common interview input format)
def build_adjacency_list(edges, directed=True):
    graph = {}
    for u, v in edges:
        if u not in graph:
            graph[u] = []
        if v not in graph:
            graph[v] = []
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

Space and lookup cost: O(V + E) space. Checking if an edge exists takes O(degree of vertex).

Adjacency Matrix

The adjacency matrix uses a 2D array where matrix[i][j] indicates whether an edge exists from vertex i to vertex j.

# Unweighted graph with vertices 0-3
matrix = [
    [0, 1, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

# Checking if an edge exists: O(1)
has_edge = matrix[0][1] == 1  # True: edge from 0 to 1

Space and lookup cost: O(V^2) space. Edge lookup is O(1), but iterating over all neighbors of a vertex takes O(V).

Interview tip: Use an adjacency list unless the problem specifically benefits from O(1) edge lookups (rare in interviews). Most interviewers expect adjacency lists.

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of the current vertex before moving to the next level. It uses a queue and is the go-to algorithm for finding the shortest path in an unweighted graph.

Implementation

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

Shortest Path in Unweighted Graph

def bfs_shortest_path(graph, start, target):
    if start == target:
        return [start]
    parent = {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor in parent:
                continue
            parent[neighbor] = vertex
            if neighbor == target:
                path = [target]
                while path[-1] != start:
                    path.append(parent[path[-1]])
                return path[::-1]
            queue.append(neighbor)
    return []  # No path found

Multi-Source BFS

Some problems require starting BFS from multiple sources simultaneously. This is common in problems like "rotting oranges" or "walls and gates."

def multi_source_bfs(grid, sources):
    if not grid or not grid[0]:
        return grid
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    visited = set()

    for r, c in sources:
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == -1:
            raise ValueError("Source must be a non-wall cell")
        if (r, c) in visited:
            continue
        grid[r][c] = 0
        queue.append((r, c, 0))  # row, col, distance
        visited.add((r, c))

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        r, c, dist = 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
                    and grid[nr][nc] != -1):  # -1 represents walls
                visited.add((nr, nc))
                grid[nr][nc] = dist + 1
                queue.append((nr, nc, dist + 1))

    return grid

Time complexity: O(V + E) for the adjacency-list traversal and parent-map shortest-path implementation below; reconstructing one path adds at most O(V). On a grid, the bound is O(rows × columns).

When to use BFS:

• Shortest path in unweighted graphs
• Level-order traversal of trees
• Finding all nodes within a given distance
• Problems involving "minimum number of steps"

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion, which implicitly uses the call stack). DFS is the foundation for many graph algorithms including cycle detection, topological sort, and finding connected components.

Recursive Implementation

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    result = []
    def visit(node):
        if node in visited:
            return
        visited.add(node)
        result.append(node)
        for neighbor in graph[node]:
            visit(neighbor)
    visit(vertex)
    return result

Iterative Implementation

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)

            # Add neighbors in reverse order for consistent traversal
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return result

DFS on a Grid

Many interview problems represent the graph as a 2D grid. Here is a template for grid-based DFS:

def dfs_grid(grid, row, col, visited):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    if (row < 0 or row >= rows or col < 0 or col >= cols
            or (row, col) in visited or grid[row][col] == 0):
        return 0

    visited.add((row, col))
    count = 1

    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        count += dfs_grid(grid, row + dr, col + dc, visited)

    return count

# Example: Count islands (number of connected components of 1s)
def count_islands(grid):
    visited = set()
    islands = 0

    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1 and (r, c) not in visited:
                dfs_grid(grid, r, c, visited)
                islands += 1

    return islands

Time complexity: O(V + E) for adjacency list, O(V^2) for adjacency matrix.

When to use DFS:

• Detecting cycles
• Topological sorting
• Finding connected components
• Path existence problems
• Exhaustive search (all paths, all combinations)

Topological Sort

Topological sort produces a linear ordering of vertices in a DAG such that for every directed edge (u, v), vertex u comes before v. This is essential for dependency resolution problems.

Kahn's Algorithm (BFS-based)

from collections import deque

def topological_sort_kahn(graph, num_vertices):
    # Calculate in-degrees
    in_degree = {v: 0 for v in graph}
    for vertex in graph:
        for neighbor in graph[vertex]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

    # Start with vertices that have no incoming edges
    queue = deque([v for v in in_degree if in_degree[v] == 0])
    result = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)

        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If result contains all vertices, the graph has a valid topological order
    if len(result) == num_vertices:
        return result
    else:
        return []  # Graph has a cycle

DFS-based Topological Sort

def topological_sort_dfs(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {vertex: WHITE for vertex in graph}
    order = []
    def visit(vertex):
        if color[vertex] == GRAY:
            return False
        if color[vertex] == BLACK:
            return True
        color[vertex] = GRAY
        for neighbor in graph[vertex]:
            if not visit(neighbor):
                return False
        color[vertex] = BLACK
        order.append(vertex)
        return True
    for vertex in graph:
        if color[vertex] == WHITE and not visit(vertex):
            return []  # A directed cycle prevents a topological order
    return order[::-1]

Common interview problems using topological sort:

• Course Schedule (can you finish all courses given prerequisites?)
• Build order for software packages
• Task scheduling with dependencies
• Alien dictionary (determine character ordering from a sorted list of words)

Time complexity: O(V + E).

Shortest Path: Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It is one of the most important algorithms for interviews.

Implementation with Min-Heap

import heapq
from itertools import count

def dijkstra(graph, start):
    # graph: {vertex: [(neighbor, weight), ...]}
    if start not in graph:
        raise ValueError('Start vertex is absent')
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError('Dijkstra requires nonnegative weights')
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    previous = {vertex: None for vertex in graph}
    sequence = count()
    min_heap = [(0, next(sequence), start)]  # tie-break without comparing labels

    while min_heap:
        current_dist, _, current_vertex = heapq.heappop(min_heap)

        # Skip if we have already found a shorter path
        if current_dist > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_vertex
                heapq.heappush(min_heap, (distance, next(sequence), neighbor))

    return distances, previous

def reconstruct_path(previous, start, target):
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    return path if path[0] == start else []

Example Usage

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3), ('C', 1)],
    'C': [('D', 1), ('E', 5)],
    'D': [('E', 2)],
    'E': []
}

distances, previous = dijkstra(graph, 'A')
# distances: {'A': 0, 'B': 4, 'C': 2, 'D': 3, 'E': 5}

path = reconstruct_path(previous, 'A', 'E')
# path: ['A', 'C', 'D', 'E']

Time complexity: O(V + E log(E + 1)) for this lazy binary-heap implementation, with O(V + E) auxiliary space in the worst case. For a simple graph, log E is O(log V).

Key constraint: Dijkstra does not work with negative edge weights. Use Bellman-Ford instead.

Shortest Path: Bellman-Ford Algorithm

Bellman-Ford finds the shortest path from a source vertex to all other vertices and works with negative edge weights. It can also detect negative cycles.

Implementation

def bellman_ford(vertices, edges, start):
    # edges: list of (u, v, weight)
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative cycle")

    return distances

Time complexity: O(V * E), which is slower than Dijkstra but handles negative weights.

When to use Bellman-Ford over Dijkstra:

• The graph has negative edge weights
• You need to detect negative cycles
• The problem asks for shortest path with at most K stops (modify the outer loop to run K times)

Shortest Path with at Most K Stops

def shortest_path_k_stops(vertices, edges, start, target, k):
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0

    for _ in range(k + 1):
        # Use a copy to ensure we only use paths from the previous iteration
        temp = distances.copy()
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < temp[v]:
                temp[v] = distances[u] + weight
        distances = temp

    return distances[target] if distances[target] != float('inf') else -1

All-pairs shortest paths: Floyd–Warshall

Floyd–Warshall considers each vertex as a possible intermediate point between every pair of endpoints. Use it when you need many pairwise distances and can afford O(V³) time and O(V²) space. A fixed vertex-count cutoff is not a performance guarantee: language, hardware and the time limit matter.

def floyd_warshall(edges, n):
    if n < 0:
        raise ValueError("Vertex count must be nonnegative")
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, weight in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("Edge endpoint is outside 0..n-1")
        dist[u][v] = min(dist[u][v], weight)
    for k in range(n):
        for i in range(n):
            if dist[i][k] == float('inf'):
                continue
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    if any(dist[i][i] < 0 for i in range(n)):
        raise ValueError("Graph contains a negative cycle")
    return dist

This directed-graph implementation uses integer vertices 0 through n − 1. It keeps the cheapest of parallel edges, preserves zero-length self-distance unless a negative cycle exists, and represents unreachable pairs with infinity. It rejects a negative cycle anywhere in the graph; finite shortest distances are not defined for pairs that can reach and leave such a cycle. For undirected inputs, include both directed edges. Negative undirected edges create negative closed walks under the usual shortest-walk formulation.

Minimum Spanning Tree: Kruskal's Algorithm

A Minimum Spanning Tree (MST) is a subset of edges that connects all vertices with the minimum total edge weight, forming a tree (no cycles). Kruskal's algorithm builds the MST by sorting all edges by weight and adding them greedily, using Union-Find to avoid cycles.

Implementation

def kruskal(vertices, edges):
    # edges: list of (weight, u, v)
    edges = sorted(edges, key=lambda edge: edge[0])  # Do not compare labels or mutate input
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return False  # Already connected, adding would create a cycle
        if rank[root_x] < rank[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_y] = root_x
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1
        return True

    mst = []
    total_weight = 0

    for weight, u, v in edges:
        if union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == len(vertices) - 1:
                break  # MST is complete

    return mst, total_weight

Time complexity: O(V + E log(E + 1)) including initialization and sorting. A disconnected input produces a minimum spanning forest; require V − 1 chosen edges when the problem requires a spanning tree and V is positive.

Minimum Spanning Tree: Prim's Algorithm

Prim's algorithm builds the MST by starting from any vertex and repeatedly adding the cheapest edge that connects a vertex in the MST to one outside it.

Implementation

import heapq
from itertools import count

def prim(graph, start):
    # graph: {vertex: [(neighbor, weight), ...]}
    if not graph:
        return [], 0
    if start not in graph:
        raise ValueError("Start vertex is absent")
    sequence = count()
    mst = []
    total_weight = 0
    visited = set([start])
    # Push all edges from start into the heap
    edges = [(weight, next(sequence), start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)

    while edges and len(visited) < len(graph):
        weight, _, u, v = heapq.heappop(edges)

        if v in visited:
            continue

        visited.add(v)
        mst.append((u, v, weight))
        total_weight += weight

        for neighbor, edge_weight in graph[v]:
            if neighbor not in visited:
                heapq.heappush(edges, (edge_weight, next(sequence), v, neighbor))

    return mst, total_weight

Time complexity: O(V + E log(E + 1)) for the lazy edge heap below, with O(V + E) auxiliary space. On a disconnected graph this implementation returns the tree of the start vertex’s component, not a spanning tree of the entire graph.

Kruskal vs Prim:

• Kruskal works well with edge lists and sparse graphs
• Prim works well with adjacency lists and dense graphs
• In interviews, Kruskal is often easier to implement because Union-Find is a clean, reusable structure

Cycle Detection

Detecting cycles is a fundamental graph operation that appears in many interview problems.

Cycle Detection in Undirected Graphs (DFS)

def has_cycle_undirected(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True  # Found a cycle
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    return False

Cycle Detection in Directed Graphs (Three-Color DFS)

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}

    def dfs(vertex):
        color[vertex] = GRAY  # Currently being processed

        for neighbor in graph[vertex]:
            if color[neighbor] == GRAY:
                return True  # Back edge found, cycle exists
            if color[neighbor] == WHITE and dfs(neighbor):
                return True

        color[vertex] = BLACK  # Fully processed
        return False

    for vertex in graph:
        if color[vertex] == WHITE:
            if dfs(vertex):
                return True
    return False

Time complexity: O(V + E) for both approaches.

Union-Find (Disjoint Set Union)

Union-Find is a data structure that efficiently tracks a collection of disjoint sets. It supports two operations: finding the root of a set and merging two sets. With path compression and union by rank, both operations run in near-constant time.

Complete Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # Number of connected components

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # Already in the same set

        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_count(self):
        return self.count

Example: Number of Connected Components

def count_components(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.get_count()

Time complexity: O(alpha(n)) amortized per operation with path compression and union by rank; initialization takes O(n). The amortized bound describes a sequence of operations, not a constant-time guarantee for each call.

Common Union-Find problems:

• Number of connected components
• Detecting cycles in undirected graphs
• Kruskal's MST algorithm
• Accounts merge
• Redundant connection
• Number of provinces

Common Interview Patterns

Understanding these recurring patterns will help you recognize which algorithm to apply.

Pattern 1: Shortest Path in Unweighted Graph

Use BFS. If the graph is a grid, treat each cell as a node with edges to its four (or eight) neighbors.

Example problems: Word Ladder, Shortest Bridge, Open the Lock.

Pattern 2: Shortest Path in Weighted Graph

Use Dijkstra if all weights are non-negative. Use Bellman-Ford if there are negative weights or if you need to detect negative cycles.

Example problems: Network Delay Time, Cheapest Flights Within K Stops, Path with Maximum Probability. You can practice all three, along with related exercises, in the shortest path LeetCode problems collection, which offers hints and step-by-step explanations.

Pattern 3: Dependency Ordering

Use topological sort. Check for cycles first (if a cycle exists, no valid ordering is possible).

Example problems: Course Schedule, Course Schedule II, Alien Dictionary.

Pattern 4: Connected Components

Use BFS, DFS, or Union-Find to identify connected components.

Example problems: Number of Islands, Number of Provinces, Accounts Merge.

Pattern 5: Cycle Detection

Use DFS with three-color marking for directed graphs. Use DFS with parent tracking or Union-Find for undirected graphs.

Example problems: Course Schedule (cycle in prerequisites), Redundant Connection, Graph Valid Tree.

Pattern 6: Minimum Cost to Connect

Use Kruskal or Prim for MST problems.

Example problems: Min Cost to Connect All Points, Optimize Water Distribution in a Village.

Pattern 7: Grid as Graph

Treat the grid as an implicit graph where each cell is a node and edges connect adjacent cells. Apply BFS or DFS depending on the problem.

Example problems: Number of Islands, Rotting Oranges, Flood Fill, Surrounded Regions, Pacific Atlantic Water Flow.

Pattern 8: Bipartite Check

Use BFS or DFS with two-coloring to check if a graph is bipartite.

from collections import deque

def is_bipartite(graph):
    color = {}

    def bfs(start):
        queue = deque([start])
        color[start] = 0

        while queue:
            vertex = queue.popleft()
            for neighbor in graph[vertex]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[vertex]
                    queue.append(neighbor)
                elif color[neighbor] == color[vertex]:
                    return False
        return True

    for vertex in graph:
        if vertex not in color:
            if not bfs(vertex):
                return False
    return True

Example problems: Is Graph Bipartite?, Possible Bipartition.

Related reading: Top 10 LeetCode Patterns You Must Know for Coding Interviews in 2026.

Worked connectivity exercise: connecting server groups

Suppose five servers already form two connected components, {A, B, C} and {D, E}. If you may add a direct connection between any two servers, one new edge joins those components. In general, C nonempty connected components need C − 1 added edges, with zero needed for an empty network. The quantity V − C is the number of edges in a spanning forest of the existing components; it is not the number of new connections needed to connect the whole network.

State whether you are adding cables, moving existing cables or choosing among candidate links. With arbitrary new links, counting components is enough. If you can only rewire existing cables, also check that at least V − 1 cables exist for V positive. If potential links have costs or restrictions, the component count alone does not find the cheapest feasible connection. Count components with BFS, DFS or union-find, then solve the actual connection problem defined by the constraints.

Practice Strategy

Graph problems can feel overwhelming because of the number of algorithms involved. Here is a structured approach to mastering them. The four weeks below focus only on graphs; if you are studying other topics too, the twelve-week LeetCode study plan for busy professionals shows where graphs fit in a longer schedule.

Week 1: Foundations

• Implement BFS and DFS from scratch without looking at references
• Solve five grid-based problems using both BFS and DFS
• Practice building adjacency lists from different input formats (edge list, adjacency matrix, grid)

Week 2: Topological Sort and Cycle Detection

• Implement both Kahn's algorithm and DFS-based topological sort
• Solve Course Schedule I and II
• Implement cycle detection for both directed and undirected graphs

Week 3: Shortest Path

• Implement Dijkstra's algorithm with a min-heap
• Implement Bellman-Ford
• Solve Network Delay Time, Cheapest Flights Within K Stops, and Path with Minimum Effort

Week 4: Union-Find and MST

• Implement Union-Find with path compression and union by rank
• Solve Number of Connected Components, Redundant Connection, and Accounts Merge
• Implement Kruskal's algorithm using your Union-Find implementation

Use PhantomCodeAI to practice these problems in a realistic interview environment. The AI-powered feedback will help you identify gaps in your approach and optimize your solutions in real time.

Complexity Reference Table

Conclusion

Graph algorithms are a core part of the coding interview toolkit. The key to mastering them is not memorizing every algorithm but understanding when to apply each one. When you see a problem, ask yourself these questions:

1. Is this a graph problem? Look for relationships between entities, grids, networks, or dependencies.
2. What type of graph is it? Directed or undirected, weighted or unweighted, cyclic or acyclic.
3. What am I looking for? Shortest path, connected components, ordering, cycles, or minimum cost.

These questions narrow the choice. Check additional constraints such as state size, negative cycles and a limit on the number of edges before selecting an implementation.

Practice implementing each algorithm from scratch until you can write them without reference. Then focus on recognizing patterns in problems so you can quickly map a new problem to a known algorithm. PhantomCodeAI provides an excellent platform for practicing graph problems with AI-guided feedback, helping you build the pattern recognition skills that make the difference in a real interview.

Practise by modelling a small system, stating the required output and checking the result on a counterexample. Understanding why an algorithm applies is more useful than memorising a template without its assumptions.

Further reading

For formal treatments and implementation alternatives, see Princeton’s shortest-path notes and minimum-spanning-tree notes. The examples here are a separate Python study implementation; check each example’s stated input assumptions.