Interview Guide: Adjacency Matrices Problems and Solutions

What is an Adjacency Matrix?

An adjacency matrix is a square grid (2D array) used to represent a finite graph. Each cell matrix[i][j] indicates whether an edge exists from vertex i to vertex j. For an unweighted graph, the value is typically 1 (edge present) or 0 (no edge). For weighted graphs, the cell holds the edge weight, often using a sentinel like 0 or ∞ to indicate no connection.

The matrix has dimensions V × V where V is the number of vertices. Because of its fixed size, it provides O(1) edge lookup — you can instantly check whether two nodes are connected by indexing into the matrix. This makes it particularly powerful for dense graphs where most pairs of vertices are connected.

Visual Representation

Consider a simple directed graph with 4 vertices (0 through 3) and edges: 0→1, 0→2, 1→2, 2→3, and 3→0. The corresponding adjacency matrix looks like this:

  0  1  2  3
0[0, 1, 1, 0]
1[0, 0, 1, 0]
2[0, 0, 0, 1]
3[1, 0, 0, 0]

Row i represents outgoing edges from vertex i, and column j represents incoming edges to vertex j. For undirected graphs, the matrix is symmetric across the main diagonal because an edge between i and j implies both directions.

Why Adjacency Matrices Matter in Technical Interviews

Interviewers love adjacency matrix problems because they test a candidate's ability to:

• Think in multiple dimensions — reasoning about a 2D structure forces you to manage row/column relationships carefully.
• Translate between representations — you may need to convert a matrix to an adjacency list and vice versa, demonstrating fluency with graph fundamentals.
• Optimize for dense graphs — matrices shine when edges are plentiful; knowing when to choose matrix over list shows architectural awareness.
• Implement classic algorithms — BFS, DFS, Dijkstra, Floyd-Warshall, and transitive closure all have elegant matrix-based implementations.

Matrix-based graph problems appear frequently at companies like Google, Meta, Amazon, and Microsoft. They span difficulty from easy (counting edges) to hard (finding all-pairs shortest paths with path reconstruction). Mastering this representation gives you a reliable fallback when an adjacency list approach becomes cumbersome due to edge density.

How to Build and Use an Adjacency Matrix

Before diving into problems, let's establish the fundamental operations you'll need in any interview setting.

Creating a Matrix from Scratch

Here's how to initialize an adjacency matrix for an unweighted, directed graph in Python. We'll use 0 for no edge and 1 for an edge.

def create_adjacency_matrix(num_vertices: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    """
    Build an adjacency matrix from a list of directed edges.
    edges is a list of (source, destination) tuples.
    """
    # Initialize V×V matrix filled with zeros
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    for src, dst in edges:
        matrix[src][dst] = 1  # Directed edge from src to dst
    
    return matrix

# Example usage
V = 4
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 0)]
adj_matrix = create_adjacency_matrix(V, edges)

for row in adj_matrix:
    print(row)
# Output:
# [0, 1, 1, 0]
# [0, 0, 1, 0]
# [0, 0, 0, 1]
# [1, 0, 0, 0]

Creating a Weighted Matrix

For weighted graphs, replace 1 with the actual weight and use float('inf') or a large sentinel for absent edges.

def create_weighted_matrix(num_vertices: int, weighted_edges: list[tuple[int, int, int]]) -> list[list[int]]:
    """
    Build a weighted adjacency matrix.
    weighted_edges contains (source, destination, weight) tuples.
    """
    INF = float('inf')
    matrix = [[INF] * num_vertices for _ in range(num_vertices)]
    
    # Distance from a node to itself is always 0
    for i in range(num_vertices):
        matrix[i][i] = 0
    
    for src, dst, weight in weighted_edges:
        matrix[src][dst] = weight
    
    return matrix

# Example
V = 5
weighted_edges = [
    (0, 1, 4), (0, 2, 1),
    (1, 3, 2),
    (2, 1, 1), (2, 3, 5),
    (3, 4, 3),
    (4, 0, 2)
]
w_matrix = create_weighted_matrix(V, weighted_edges)
print(w_matrix[0])  # [0, 4, 1, inf, inf]
print(w_matrix[2])  # [inf, 1, 0, 5, inf]

Converting Between Matrix and Adjacency List

You may need to convert an adjacency matrix to an adjacency list (common when the problem gives you a matrix but you prefer list-based traversal).

def matrix_to_adjacency_list(matrix: list[list[int]]) -> dict[int, list[int]]:
    """
    Convert an unweighted adjacency matrix to an adjacency list.
    Returns a dictionary mapping each vertex to its list of neighbors.
    """
    adj_list = {i: [] for i in range(len(matrix))}
    
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == 1:  # Edge exists
                adj_list[i].append(j)
    
    return adj_list

def adjacency_list_to_matrix(adj_list: dict[int, list[int]], num_vertices: int) -> list[list[int]]:
    """
    Reverse conversion: adjacency list back to matrix.
    """
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for src, neighbors in adj_list.items():
        for dst in neighbors:
            matrix[src][dst] = 1
    return matrix

Common Interview Problems and Solutions

Below are five classic adjacency matrix problems you're likely to encounter, each with a complete solution and detailed walkthrough.

Problem 1: Count Total Edges in an Undirected Graph

Given: An adjacency matrix for an undirected graph. Count the total number of unique edges. Since the matrix is symmetric, each edge appears twice (once in each direction), so you must divide by 2.

def count_edges_undirected(matrix: list[list[int]]) -> int:
    """
    Count unique edges in an undirected graph represented by a symmetric adjacency matrix.
    """
    total = 0
    V = len(matrix)
    
    for i in range(V):
        for j in range(i + 1, V):  # Only upper triangle to avoid double-counting
            if matrix[i][j] == 1:
                total += 1
    
    return total

# Alternatively, sum all 1s and divide by 2
def count_edges_alt(matrix: list[list[int]]) -> int:
    return sum(sum(row) for row in matrix) // 2

# Test
undirected_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 0],
    [0, 1, 0, 0]
]
print(count_edges_undirected(undirected_matrix))  # Output: 3 (edges: 0-1, 0-2, 1-2, 1-3 = 4? Let's count: 0-1, 0-2, 1-2, 1-3 = 4)
# Actually edges: 0-1, 0-2, 1-2, 1-3 = 4 edges. So output should be 4.
print(count_edges_alt(undirected_matrix))  # 4

Problem 2: Find All Nodes Reachable via BFS

Given: A directed adjacency matrix and a starting vertex. Return a list of all vertices reachable from the start using breadth-first search. This is a fundamental traversal problem that tests your ability to adapt BFS to a matrix representation.

from collections import deque

def bfs_reachable(matrix: list[list[int]], start: int) -> list[int]:
    """
    Return all vertices reachable from 'start' using BFS on an adjacency matrix.
    """
    V = len(matrix)
    visited = [False] * V
    queue = deque([start])
    visited[start] = True
    reachable = []
    
    while queue:
        current = queue.popleft()
        reachable.append(current)
        
        # Scan the row for neighbors
        for neighbor in range(V):
            if matrix[current][neighbor] == 1 and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    return reachable

# Test with a directed graph
matrix = [
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0]
]
print(bfs_reachable(matrix, 0))  # [0, 1, 2, 3, 4] — all reachable from 0
print(bfs_reachable(matrix, 3))  # [3] — no outgoing edges from 3

Problem 3: DFS Path Existence Between Two Nodes

Given: A directed adjacency matrix and two vertices src and dst. Determine whether a path exists from src to dst using depth-first search.

def dfs_path_exists(matrix: list[list[int]], src: int, dst: int) -> bool:
    """
    Check if a path exists from src to dst using DFS on an adjacency matrix.
    """
    V = len(matrix)
    visited = [False] * V
    
    def dfs(current: int) -> bool:
        if current == dst:
            return True
        
        visited[current] = True
        
        for neighbor in range(V):
            if matrix[current][neighbor] == 1 and not visited[neighbor]:
                if dfs(neighbor):
                    return True
        
        return False
    
    return dfs(src)

# Test
matrix = [
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]
print(dfs_path_exists(matrix, 0, 3))  # True (0→1→2→3)
print(dfs_path_exists(matrix, 3, 0))  # False (no outgoing edges from 3)
print(dfs_path_exists(matrix, 1, 0))  # False (edges go forward only)

Problem 4: Floyd-Warshall All-Pairs Shortest Paths

Given: A weighted adjacency matrix (with INF for no edge). Compute the shortest path between every pair of vertices using the Floyd-Warshall algorithm. This is a classic dynamic programming problem that operates directly on the matrix in O(V³) time.

def floyd_warshall(matrix: list[list[int]]) -> list[list[int]]:
    """
    Compute all-pairs shortest paths using Floyd-Warshall.
    Modifies the matrix in-place and also returns it.
    Assumes matrix[i][i] = 0 and uses INF for non-edges.
    """
    V = len(matrix)
    INF = float('inf')
    dist = [row[:] for row in matrix]  # Deep copy to avoid mutating input
    
    for k in range(V):          # Intermediate vertex
        for i in range(V):      # Source vertex
            for j in range(V):  # Destination vertex
                if dist[i][k] != INF and dist[k][j] != INF:
                    new_dist = dist[i][k] + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
    
    return dist

# Test with the weighted graph from earlier
INF = float('inf')
weighted_matrix = [
    [0, 4, 1, INF, INF],
    [INF, 0, INF, 2, INF],
    [INF, 1, 0, 5, INF],
    [INF, INF, INF, 0, 3],
    [2, INF, INF, INF, 0]
]

result = floyd_warshall(weighted_matrix)
print("Shortest distances from vertex 0:")
print(result[0])  # [0, 2, 1, 6, 9] — 0→2→1 (cost 2) beats 0→1 directly (cost 4)
print("Shortest distances from vertex 4:")
print(result[4])  # [2, 3, 3, 5, 0]

Problem 5: Detect Cycle in a Directed Graph (Matrix + DFS)

Given: A directed adjacency matrix. Return True if the graph contains a cycle. This uses DFS with a three-color marking scheme (white, gray, black) adapted to the matrix representation.

def has_cycle_directed(matrix: list[list[int]]) -> bool:
    """
    Detect a cycle in a directed graph represented by an adjacency matrix.
    Uses DFS with three states: 0 = unvisited, 1 = visiting (in current path), 2 = visited (fully processed).
    """
    V = len(matrix)
    state = [0] * V  # 0: unvisited, 1: visiting, 2: done
    
    def dfs(vertex: int) -> bool:
        state[vertex] = 1  # Mark as currently visiting
        
        for neighbor in range(V):
            if matrix[vertex][neighbor] == 1:
                if state[neighbor] == 1:
                    return True  # Back edge found → cycle
                if state[neighbor] == 0:
                    if dfs(neighbor):
                        return True
        
        state[vertex] = 2  # Mark as fully processed
        return False
    
    for v in range(V):
        if state[v] == 0:
            if dfs(v):
                return True
    
    return False

# Test: graph with a cycle
cyclic_matrix = [
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 0]  # Edge 3→0 completes the cycle 0→1→2→3→0
]
print(has_cycle_directed(cyclic_matrix))  # True

# Test: DAG (no cycle)
dag_matrix = [
    [0, 1, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]
print(has_cycle_directed(dag_matrix))  # False

Problem 6: Transitive Closure (Warshall's Algorithm)

Given: An unweighted directed adjacency matrix. Compute the transitive closure — a matrix where closure[i][j] = 1 if there exists any path (of any length) from i to j. This is essentially Floyd-Warshall for boolean reachability.

def transitive_closure(matrix: list[list[int]]) -> list[list[int]]:
    """
    Compute the transitive closure of a directed graph.
    closure[i][j] = 1 if a path exists from i to j, else 0.
    """
    V = len(matrix)
    closure = [row[:] for row in matrix]  # Start with direct edges
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # If i→k exists and k→j exists, then i→j exists
                if closure[i][k] and closure[k][j]:
                    closure[i][j] = 1
    
    return closure

# Test
matrix = [
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]
closure = transitive_closure(matrix)
for row in closure:
    print(row)
# Output:
# [0, 1, 1, 1]  — 0 can reach 1, 2, 3 via chain
# [0, 0, 1, 1]  — 1 can reach 2, 3
# [0, 0, 0, 1]  — 2 can reach 3
# [0, 0, 0, 0]  — 3 reaches nothing

Problem 7: Find Number of Connected Components (Undirected)

Given: A symmetric adjacency matrix for an undirected graph. Count the number of connected components using BFS or DFS.

def count_components_undirected(matrix: list[list[int]]) -> int:
    """
    Count connected components in an undirected graph using BFS.
    Assumes the matrix is symmetric (undirected).
    """
    V = len(matrix)
    visited = [False] * V
    components = 0
    
    for vertex in range(V):
        if not visited[vertex]:
            components += 1
            # BFS from this unvisited vertex
            queue = deque([vertex])
            visited[vertex] = True
            while queue:
                curr = queue.popleft()
                for neighbor in range(V):
                    if matrix[curr][neighbor] == 1 and not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
    
    return components

# Test: graph with two disconnected components
undirected = [
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 0, 1, 1, 0]
]
print(count_components_undirected(undirected))  # 2 (component A: 0,1; component B: 2,3,4)

Problem 8: Dijkstra's Shortest Path from Single Source

Given: A weighted adjacency matrix and a starting vertex. Return the shortest distances to all other vertices using Dijkstra's algorithm. While Dijkstra is more commonly implemented with adjacency lists and a priority queue, the matrix version is straightforward and worth knowing.

import heapq

def dijkstra_matrix(matrix: list[list[int]], start: int) -> list[int]:
    """
    Compute shortest distances from 'start' to all vertices using Dijkstra.
    matrix uses INF for no edge and 0 on the diagonal.
    """
    V = len(matrix)
    INF = float('inf')
    distances = [INF] * V
    distances[start] = 0
    visited = [False] * V
    # Priority queue stores (distance, vertex)
    pq = [(0, start)]
    
    while pq:
        dist, current = heapq.heappop(pq)
        
        if visited[current]:
            continue
        visited[current] = True
        
        # Relax all outgoing edges
        for neighbor in range(V):
            weight = matrix[current][neighbor]
            if weight != INF and weight != 0:  # Skip self-loops with weight 0 and non-edges
                new_dist = dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
    
    return distances

# Test
INF = float('inf')
weighted_matrix = [
    [0, 4, 1, INF, INF],
    [INF, 0, INF, 2, INF],
    [INF, 1, 0, 5, INF],
    [INF, INF, INF, 0, 3],
    [2, INF, INF, INF, 0]
]
print(dijkstra_matrix(weighted_matrix, 0))
# Expected: [0, 2, 1, 6, 9]
# Explanation: 0→2 (cost 1), 0→2→1 (cost 2), 0→2→1→3 (cost 6), 0→2→1→3→4 (cost 9)

Best Practices and Optimization Tips

When working with adjacency matrices in interviews, keep these principles in mind:

• Choose the right representation for the graph density. If the graph has V=1000 but only ~50 edges, an adjacency matrix wastes O(V²) memory and makes scanning neighbors O(V) per vertex. Use adjacency lists for sparse graphs. For dense graphs (E ≈ V²), the matrix gives O(1) edge lookup that lists can't match.
• Avoid iterating over the entire row naively. When you need to find all neighbors of a vertex in a sparse matrix, consider maintaining a parallel list of actual neighbors to avoid O(V) scans. If the problem doesn't allow pre-processing, mention the trade-off to your interviewer.
• Use sentinel values carefully. For weighted graphs, float('inf') works well in Python, but in languages like Java or C++, use Integer.MAX_VALUE or a large constant like 10^9. Always check for overflow when adding weights.
• Leverage symmetry in undirected graphs. When the matrix is symmetric, you only need to scan the upper or lower triangle for certain operations (like edge counting), cutting work in half.
• Modify the matrix in-place when permitted. Algorithms like Floyd-Warshall and transitive closure can mutate the input matrix to save memory. Always ask your interviewer if in-place modification is acceptable.
• Handle self-loops explicitly. A self-loop (matrix[i][i] == 1) can cause infinite recursion in DFS/BFS if not handled. For shortest paths, the diagonal should be 0 (distance to self is zero). Clarify with the interviewer whether self-loops exist.
• Consider converting to adjacency list for traversal-heavy problems. If the problem involves many BFS/DFS traversals on a sparse matrix, converting to an adjacency list first (O(V²) one-time cost) can make each traversal O(V+E) instead of O(V²).

Performance Comparison: Matrix vs. Adjacency List

# Demonstrating the neighbor-scanning cost difference
import time

def benchmark_neighbor_scan():
    V = 5000
    # Dense matrix: all pairs connected (except self)
    dense_matrix = [[1 if i != j else 0 for j in range(V)] for i in range(V)]
    # Sparse list: each node connects to only 5 random neighbors
    sparse_list = {i: [(i + j) % V for j in range(1, 6)] for i in range(V)}
    
    # Time matrix neighbor scan for vertex 0
    start = time.perf_counter()
    neighbors_matrix = [j for j in range(V) if dense_matrix[0][j] == 1]
    end = time.perf_counter()
    print(f"Matrix scan (V={V}): {(end - start)*1000:.3f} ms")
    
    # Time list neighbor retrieval for vertex 0
    start = time.perf_counter()
    neighbors_list = sparse_list[0]
    end = time.perf_counter()
    print(f"List retrieval (V={V}): {(end - start)*1000:.6f} ms")

# Uncomment to run (slow for V=5000 dense matrix scan)
# benchmark_neighbor_scan()
# Matrix scan must check all V entries, while list retrieval is O(degree)

Template: BFS/DFS Skeleton for Adjacency Matrices

Here's a reusable skeleton you can adapt quickly during an interview:

from collections import deque

def traverse_matrix(matrix: list[list[int]], start: int, use_bfs: bool = True):
    """
    Generic traversal skeleton for adjacency matrices.
    Set use_bfs=True for BFS, False for DFS.
    """
    V = len(matrix)
    visited = [False] * V
    container = deque([start]) if use_bfs else [start]  # Queue for BFS, Stack for DFS
    visited[start] = True
    result = []
    
    while container:
        # BFS: pop left; DFS: pop right
        current = container.popleft() if use_bfs else container.pop()
        result.append(current)
        
        for neighbor in range(V):
            if matrix[current][neighbor] == 1 and not visited[neighbor]:
                visited[neighbor] = True
                container.append(neighbor)
    
    return result

Conclusion

Adjacency matrices are a cornerstone of graph representation in technical interviews. They offer constant-time edge queries and lend themselves beautifully to algorithms like Floyd-Warshall, transitive closure, and dense-graph Dijkstra. The key to mastering them is recognizing the density trade-off: when edges are plentiful, the matrix is your best friend; when the graph is sparse, an adjacency list will serve you better. By internalizing the patterns in this guide — BFS/DFS adaptation, cycle detection, all-pairs shortest paths, and component counting — you'll be equipped to handle virtually any adjacency matrix problem that comes your way. Practice converting between representations, reasoning about symmetry, and choosing the optimal algorithm for the graph density at hand, and you'll walk into your next interview with confidence and clarity.