Understanding Adjacency Matrix Graph in Computer Science

1. Introduction and Core Concepts

An adjacency matrix graph is one of the most fundamental and intuitive ways to represent a graph data structure in computer science. At its core, a graph consists of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. The adjacency matrix provides a systematic, tabular method for encoding these connections using a two-dimensional square matrix, where both rows and columns correspond to the vertices of the graph. If an edge exists between vertex i and vertex j, the cell at position [i][j] contains a value indicating the presence of that connection, typically 1 for unweighted graphs or a weight value for weighted graphs.

The importance of the adjacency matrix graph lies in its simplicity and its power for certain classes of problems. Unlike more complex pointer-based structures, the matrix offers constant-time access to edge information. This makes it exceptionally valuable in scenarios where the primary operation is frequently checking whether two vertices are directly connected. For dense graphs, where the number of edges is close to the maximum possible number of edges, the adjacency matrix is also highly space-efficient in a practical sense, as it avoids the overhead of maintaining linked lists or dynamic arrays for each vertex.

Understanding the adjacency matrix graph is essential for any computer science student, software engineer, or data scientist because it forms the foundation for numerous advanced algorithms. Many classic graph algorithms, including Floyd-Warshall for all-pairs shortest paths, transitive closure computations, and spectral graph theory operations, are naturally expressed as matrix operations. Furthermore, the matrix representation bridges graph theory and linear algebra, allowing powerful mathematical tools to be applied to network analysis, recommendation systems, and social network modeling. Mastering this representation provides insight into the trade-offs between different data structures and helps in selecting the right tool for a given computational problem.

Why the Matrix Representation Matters

The choice of graph representation has profound implications for performance, and the adjacency matrix graph excels in specific contexts. For algorithmic design, its predictable structure simplifies implementation and reasoning. There is no need to traverse adjacency lists or handle variable-length data structures; every potential edge has a dedicated, addressable location. This regularity is particularly advantageous for hardware acceleration and parallel processing, where matrix operations can be heavily optimized using vectorized instructions and GPU computing.

Moreover, the adjacency matrix graph provides a complete and unambiguous view of the entire graph topology at a glance. For small to medium-sized graphs, visualizing the matrix can immediately reveal patterns such as isolated vertices (rows or columns of all zeros), cliques (fully dense submatrices), or bipartite structures. This holistic view is invaluable for debugging, teaching, and theoretical analysis, making the adjacency matrix not just a storage mechanism but also an analytical lens for understanding graph properties.

2. How It Works

The mechanism behind an adjacency matrix graph is elegantly straightforward. Consider a graph G = (V, E) with n vertices, labeled from 0 to n-1. The adjacency matrix is an n x n matrix, denoted as Adj, where Adj[i][j] stores information about the edge from vertex i to vertex j. For an unweighted, undirected graph, Adj[i][j] = 1 if there is an edge between i and j, and 0 otherwise. Because the graph is undirected, the matrix is symmetric, meaning Adj[i][j] == Adj[j][i] for all i and j. The diagonal entries Adj[i][i] are typically 0, unless the graph allows self-loops.

For a directed graph, or digraph, the symmetry property no longer holds. In this case, Adj[i][j] = 1 indicates a directed edge from i to j, but does not imply an edge from j to i. This directionality is captured naturally by the asymmetry of the matrix. For weighted graphs, the binary 0/1 values are replaced by the weight of the edge. A common convention is to use 0 or infinity (INF) to denote the absence of an edge, and the actual weight w(i,j) to denote its presence. For example, in a road network graph, the entry might store the distance or travel time between two cities.

Operations on the adjacency matrix graph are performed through direct index access. To check if an edge exists between vertex u and vertex v, you simply examine Adj[u][v]. To add an edge, you set Adj[u][v] = 1 (and Adj[v][u] = 1 for undirected graphs). To remove an edge, you set the corresponding entry back to 0. Iterating over all neighbors of a vertex u requires scanning the entire row Adj[u], checking which columns contain non-zero values. This row-scan operation is central to traversals like Breadth-First Search (BFS) and Depth-First Search (DFS) when using a matrix.

Undirected vs. Directed and Weighted Variants

The flexibility of the adjacency matrix graph allows it to model diverse graph types with minimal modification. In an undirected graph, the matrix is symmetric and only the upper or lower triangular portion is strictly necessary, though the full matrix is usually stored for simplicity. In a directed graph, the out-degree of a vertex i is the sum of row i, while the in-degree is the sum of column i. This makes degree calculations a simple matter of row or column summation.

For weighted graphs, the matrix becomes a weight matrix. An entry of 0 might be ambiguous—it could mean no edge or an edge with zero weight—so implementations often use a sentinel value like None, float('inf'), or a separate boolean matrix to distinguish absence from zero-weight. This weighted adjacency matrix is the direct input for algorithms like Floyd-Warshall and for representing Markov chains, where entries represent transition probabilities. The ability to store rich edge information in a single, uniform structure is a key strength of this representation.

3. Implementation

Implementing an adjacency matrix graph in Python is straightforward using nested lists or the NumPy library for better performance. The most basic approach uses a list of lists, where each inner list represents a row of the matrix. This approach is ideal for learning and for graphs where n is relatively small, typically a few thousand vertices or fewer. The implementation centers around a class that encapsulates the matrix and provides methods for core graph operations.

Below is a foundational implementation of an unweighted, undirected adjacency matrix graph. It demonstrates initialization, edge insertion, edge removal, and edge query operations with clear, commented code.

# Basic Adjacency Matrix for Unweighted Undirected Graph
class AdjacencyMatrixGraph:
    def __init__(self, num_vertices):
        self.n = num_vertices
        # Initialize n x n matrix with all zeros
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        # Validate vertex indices
        if 0 <= u < self.n and 0 <= v < self.n:
            self.matrix[u][v] = 1
            self.matrix[v][u] = 1  # For undirected graph, mirror the edge

    def remove_edge(self, u, v):
        if 0 <= u < self.n and 0 <= v < self.n:
            self.matrix[u][v] = 0
            self.matrix[v][u] = 0

    def has_edge(self, u, v):
        if 0 <= u < self.n and 0 <= v < self.n:
            return self.matrix[u][v] == 1
        return False

    def get_neighbors(self, u):
        # Scan the entire row to find neighbors - O(n) operation
        neighbors = []
        for v in range(self.n):
            if self.matrix[u][v] == 1:
                neighbors.append(v)
        return neighbors

# Example usage
g = AdjacencyMatrixGraph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
print(g.has_edge(0, 1))  # True
print(g.get_neighbors(0)) # [1, 2]

For weighted and directed graphs, the implementation requires only slight adjustments. Instead of storing binary values, the matrix stores weights, and for directed graphs, we remove the mirroring step. Using a sentinel value like float('inf') for absent edges makes algorithms that rely on weight comparisons much cleaner.

# Weighted Directed Graph using Adjacency Matrix
import math

class WeightedDigraphMatrix:
    def __init__(self, num_vertices):
        self.n = num_vertices
        # Use infinity to denote no edge, 0 on diagonal
        self.matrix = [[math.inf for _ in range(num_vertices)] for _ in range(num_vertices)]
        for i in range(num_vertices):
            self.matrix[i][i] = 0

    def add_edge(self, u, v, weight):
        if 0 <= u < self.n and 0 <= v < self.n:
            self.matrix[u][v] = weight
            # No mirroring for directed graph

    def get_weight(self, u, v):
        if 0 <= u < self.n and 0 <= v < self.n:
            return self.matrix[u][v]
        return math.inf

    def has_edge(self, u, v):
        return self.get_weight(u, v) != math.inf and u != v

# Example: flight network with distances
flight_graph = WeightedDigraphMatrix(3)
flight_graph.add_edge(0, 1, 450)  # NYC -> Chicago
flight_graph.add_edge(1, 2, 280)  # Chicago -> Dallas
flight_graph.add_edge(0, 2, 900)  # NYC -> Dallas direct
print(flight_graph.get_weight(0, 1)) # 450

For performance-critical applications or large dense graphs, using NumPy provides significant advantages. NumPy arrays offer faster initialization, vectorized operations, and lower memory overhead per element compared to Python lists of lists. They also enable direct use of linear algebra routines.

import numpy as np

class NumpyAdjacencyMatrix:
    def __init__(self, num_vertices, directed=False):
        self.n = num_vertices
        self.directed = directed
        self.matrix = np.zeros((num_vertices, num_vertices), dtype=int)

    def add_edge(self, u, v):
        if 0 <= u < self.n and 0 <= v < self.n:
            self.matrix[u, v] = 1
            if not self.directed:
                self.matrix[v, u] = 1

    def get_degrees(self):
        # Vectorized degree calculation
        if self.directed:
            out_degree = np.sum(self.matrix, axis=1)
            in_degree = np.sum(self.matrix, axis=0)
            return out_degree, in_degree
        else:
            # For undirected, degree is sum of row
            return np.sum(self.matrix, axis=1)

    def square_matrix(self):
        # Matrix multiplication counts 2-step paths
        # (Adj * Adj)[i][j] = number of paths of length 2 from i to j
        return np.matmul(self.matrix, self.matrix)

# Example
np_graph = NumpyAdjacencyMatrix(4)
np_graph.add_edge(0, 1)
np_graph.add_edge(1, 2)
print(np_graph.get_degrees())
print(np_graph.square_matrix())

Traversing an adjacency matrix graph is also simple to implement. Both BFS and DFS require scanning a row to discover unvisited neighbors, which is a key difference from adjacency list traversals where neighbors are iterated directly.

from collections import deque

def bfs_adjacency_matrix(matrix, start_vertex):
    n = len(matrix)
    visited = [False] * n
    queue = deque([start_vertex])
    visited[start_vertex] = True
    traversal_order = []

    while queue:
        u = queue.popleft()
        traversal_order.append(u)
        # Scan entire row to find neighbors
        for v in range(n):
            if matrix[u][v] == 1 and not visited[v]:
                visited[v] = True
                queue.append(v)
    return traversal_order

def dfs_adjacency_matrix(matrix, start_vertex):
    n = len(matrix)
    visited = [False] * n
    result = []

    def dfs_recursive(u):
        visited[u] = True
        result.append(u)
        for v in range(n):
            if matrix[u][v] == 1 and not visited[v]:
                dfs_recursive(v)

    dfs_recursive(start_vertex)
    return result

# Test traversal
mat = [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]
print(bfs_adjacency_matrix(mat, 0)) # [0, 1, 2, 3]
print(dfs_adjacency_matrix(mat, 0)) # [0, 1, 3, 2]

4. Step-by-Step Example

To solidify the concept, let us walk through a concrete example of constructing an adjacency matrix graph. Consider an undirected, unweighted graph with four vertices labeled A, B, C, and D, which we will map to indices 0, 1, 2, and 3 respectively. The edge set is: (A-B), (A-C), (B-D), and (C-D). This forms a simple cycle with a diagonal-like structure, essentially a square.

We begin with a 4x4 matrix initialized entirely to zeros. This represents a graph with no edges. The rows and columns are ordered as A, B, C, D. At this stage, every entry Adj[i][j] is 0, indicating no connections.

Next, we add the edge A-B. For an undirected graph, this requires setting two entries: Adj[A][B] and Adj[B][A] to 1. In index terms, we set matrix[0][1] = 1 and matrix[1][0] = 1. The matrix now has two symmetric ones reflecting this single undirected connection.

We then add edge A-C. Similarly, we set matrix[0][2] = 1 and matrix[2][0] = 1. Adding edge B-D sets matrix[1][3] = 1 and matrix[3][1] = 1. Finally, adding edge C-D sets matrix[2][3] = 1 and matrix[3][2] = 1. After all four edges are added, the final adjacency matrix is complete.

The resulting matrix looks like this, with rows and columns labeled for clarity:

From this matrix, we can instantly answer graph queries. To check if A is connected to D, we look at row A, column D, which is 0, so no direct edge exists. To find all neighbors of B, we scan row B: entries at columns A and D are 1, so neighbors are {A, D}. The degree of vertex A is the sum of row A, which is 2. Notice the perfect symmetry across the main diagonal, a hallmark of undirected graphs. If this were a directed graph where edges were A->B, B->D, C->A, and D->C, the matrix would be asymmetric and would contain only four ones instead of eight.

This step-by-step construction also illustrates how to handle weighted graphs. If the edge A-B had weight 5, A-C weight 3, B-D weight 2, and C-D weight 4, the matrix would contain those weights instead of 1s, with 0 or INF elsewhere. The process remains identical: initialize, then populate specific cells based on the edge list. This deterministic mapping from edge list to matrix is what makes the adjacency matrix graph so reliable and easy to implement correctly.

5. Complexity Analysis

Complexity analysis is crucial for deciding when to use an adjacency matrix graph versus other representations. The performance characteristics are highly predictable because the matrix size is fixed at n x n, regardless of the number of edges. This leads to excellent performance for some operations but significant overhead for others, especially in sparse graphs.

The space complexity is the most prominent characteristic. An adjacency matrix graph always requires O(n^2) space, where n is the number of vertices. This is true for best, average, and worst cases. For a graph with 10,000 vertices, the matrix requires 100 million entries. If each entry is a single byte, that is 100 MB; if it is a 4-byte integer, it is 400 MB. This quadratic growth makes the matrix impractical for very large, sparse graphs such as web graphs or social networks with millions of nodes but relatively few edges per node.

Time complexity, however, shows a more nuanced picture. Checking for the existence of an edge between u and v is O(1) in all cases—simply access matrix[u][v]. Adding or removing an edge is also O(1). These constant-time operations are the primary advantage of the matrix. Conversely, operations that require iterating over neighbors are expensive. Finding all neighbors of a vertex, or iterating over all edges, requires scanning a row or the entire matrix, leading to O(n) and O(n^2) time respectively.

The following table summarizes the time and space complexity for common operations on an adjacency matrix graph. Note that n represents the number of vertices and e represents the number of edges.

It is important to interpret this table in context. For dense graphs where e is close to n^2, the O(n^2) traversal cost is actually optimal, since you must process nearly n^2 edges anyway. In that scenario, the matrix is not wasteful. For sparse graphs where e is much smaller than n^2, such as e = O(n), the O(n^2) traversal is highly inefficient compared to an adjacency list's O(n + e) traversal. Therefore, the decision to use an adjacency matrix graph should be driven by graph density and the frequency of edge-existence queries versus neighbor-iteration operations in your workload.

6. Variations and Optimizations

While the standard adjacency matrix graph is simple, several variations and optimizations exist to address its limitations, particularly its high space consumption. These adapted forms retain the core benefits of fast edge lookup while mitigating memory overhead for specific graph types.

One common optimization is the use of a bitset or boolean matrix. Instead of storing integers (4 or 8 bytes per entry), a bitset stores a single bit per entry. This reduces memory usage by a factor of 32 or 64. In Python, this can be approximated using the `bitarray` library or by packing bits into integers. In languages like Java or C++, `BitSet` or `vector<bool>` provides this functionality natively. For an undirected graph, further optimization is possible by storing only the upper triangular part of the symmetric matrix. Since Adj[i][j] == Adj[j][i], storing the full matrix is redundant. A compressed representation can store n*(n-1)/2 entries instead of n^2, nearly halving memory usage, though it complicates indexing logic.

For sparse graphs, a hybrid approach or a sparse matrix representation is often preferred. Libraries like SciPy provide sparse matrix formats such as CSR (Compressed Sparse Row) and CSC (Compressed Sparse Column) that store only non-zero entries. While technically not a dense adjacency matrix, these structures preserve the matrix abstraction and allow matrix operations while using O(n + e) space. This is ideal when you need matrix algebra capabilities but cannot afford O(n^2) memory.

Another important variation is the adjacency matrix for multigraphs and graphs with self-loops. In a multigraph where multiple edges can exist between the same pair of vertices, the matrix entry stores the count of edges rather than just 0 or 1. For self-loops, the diagonal entries Adj[i][i] are set to 1 or the loop weight. These extensions make the matrix representation flexible enough to model more complex relational structures without changing the underlying data structure paradigm.

Optimizing for Cache and Parallelism

Modern hardware optimizations also play a role. Because the adjacency matrix is stored as a contiguous block of memory (especially when using NumPy), it exhibits excellent cache locality when scanning rows. This can make row scans surprisingly fast in practice, despite the O(n) theoretical cost. Furthermore, matrix operations like squaring the matrix to find paths of length two, or using matrix multiplication for transitive closure, can be parallelized efficiently on GPUs. This makes the adjacency matrix graph a preferred representation in high-performance computing and machine learning contexts where graph operations are expressed as linear algebra.

7. Real-World Applications

The adjacency matrix graph is not merely an academic exercise; it powers numerous real-world systems where dense connectivity or fast edge queries are critical. Its applications span networking, transportation, social sciences, and computer systems.

In computer networking, routing tables and network topology maps are often represented as adjacency matrices. For a network of routers or switches, the matrix indicates direct physical links. Protocols like OSPF (Open Shortest Path First) use link-state advertisements to build a complete topology map at each router, which is essentially an adjacency matrix. The Floyd-Warshall algorithm, which operates directly on the adjacency matrix, is then used to compute all-pairs shortest paths for optimal routing. Similarly, in social network analysis, a dense community or a small cohort (e.g., a classroom or corporate team) can be modeled with an adjacency matrix to quickly analyze relationships, detect cliques, and compute centrality measures via matrix operations.

In transportation and logistics, flight networks, road networks for small geographic areas, and supply chain graphs often use adjacency matrices. For airline scheduling with a few hundred airports, the matrix provides O(1) lookup to check if a direct flight exists between two cities and stores flight distances or costs as weights. Recommendation systems also leverage adjacency matrices, particularly in collaborative filtering where a user-item interaction matrix is a bipartite graph adjacency matrix. Matrix factorization techniques are then applied to this matrix to predict missing entries and generate recommendations.

Perhaps most importantly, the adjacency matrix is fundamental in scientific computing and graph algorithms research. Operations like finding the number of triangles in a graph, computing graph spectra (eigenvalues of the adjacency matrix), or determining reachability via matrix exponentiation all rely on the matrix form. Web servers and databases may use adjacency matrices internally for dependency graphs, such as tracking dependencies between microservices or database tables, where the graph is relatively small and dense and fast dependency checks are required.

8. Comparison with Alternatives

Choosing the right graph representation is a critical design decision. The two dominant alternatives to the adjacency matrix graph are the adjacency list and the edge list. Each has distinct trade-offs in terms of space, time for different operations, and ease of implementation. Understanding these trade-offs is essential for writing efficient graph algorithms.

An adjacency list represents a graph as an array or dictionary of lists. Each vertex maintains a list of its neighbors. This is highly space-efficient for sparse graphs, requiring only O(n + e) space. An edge list simply stores a list of all edges as pairs (u, v), which is even simpler but inefficient for many queries. The adjacency matrix, with its O(n^2) space, is the most memory-intensive but offers the fastest edge queries.

The performance differences become stark when considering common operations. For example, iterating over all neighbors of a vertex is O(degree) with an adjacency list but O(n) with a matrix. Conversely, checking if an edge exists is O(degree) or O(log degree) with a list (if sorted) but O(1) with a matrix. For dense graphs, the matrix's O(n) neighbor iteration is not a disadvantage, as degree is close to n anyway. For sparse graphs, the list is vastly superior for traversals.

The following comprehensive comparison table highlights these differences to guide your selection process.

In practice, the rule of thumb is: use an adjacency matrix graph when the graph is dense (e > n^2 / 4), when you need constant-time edge existence checks, or when you plan to use matrix-based algorithms like Floyd-Warshall or spectral analysis. Use an adjacency list for sparse graphs, which constitute the majority of large real-world graphs like the web, social networks, and road networks at scale. Many modern graph libraries, such as NetworkX, even allow you to switch between representations or use hybrid structures to get the best of both worlds.

9. Common Mistakes and Best Practices

Even though the adjacency matrix graph is conceptually simple, developers frequently encounter pitfalls that lead to bugs, performance issues, or excessive memory consumption. Awareness of these common mistakes is key to using the structure effectively.

One of the most frequent mistakes is using an adjacency matrix for large sparse graphs. A developer might choose the matrix for its simplicity, not realizing that for a graph with 100,000 vertices and 200,000 edges, the matrix would require 10 billion entries, consuming tens of gigabytes of memory, while an adjacency list would need only a few megabytes. Always estimate n^2 memory cost before committing to a matrix. If n exceeds a few thousand and the graph is sparse, the matrix is almost certainly the wrong choice.

Another common error is forgetting to handle symmetry for undirected graphs. Failing to set both matrix[u][v] and matrix[v][u] when adding an edge results in a directed graph representation unintentionally, leading to incorrect traversal results and degree calculations. Similarly, for weighted graphs, using 0 to denote no edge creates ambiguity when 0 is a valid edge weight. Best practice is to use a distinct sentinel like None or math.inf and to be explicit about its meaning in code comments and documentation.

Off-by-one errors and index validation are also prevalent. Graph vertices are often labeled from 1 to n in problem descriptions, but Python lists are 0-indexed. Forgetting to convert between these conventions leads to IndexError exceptions or silent logical errors. Always validate that u and v are within [0, n-1] before accessing the matrix.

Best Practices for Robust Implementation

• Choose the right data type: For unweighted graphs, use boolean or bitset to save memory. For weighted graphs, use float('inf') for absent edges and document the convention clearly.
• Encapsulate in a class: Do not manipulate the raw 2D list directly throughout your codebase. Wrap it in a Graph class with methods like add_edge, has_edge, and get_neighbors to enforce invariants such as symmetry and bounds checking.
• Use NumPy for dense graphs: If n is greater than 500 and the graph is dense, prefer NumPy arrays over lists of lists for better performance and memory efficiency. Leverage vectorized operations for degree and path computations.
• Consider immutability for algorithms: When running algorithms like Floyd-Warshall that modify the matrix, work on a copy to preserve the original graph structure for later use or debugging.
• Profile before optimizing: If neighbor iteration is a bottleneck, measure whether the O(n) scan is actually problematic. For dense graphs, it may be unavoidable and acceptable. For sparse graphs, switch to an adjacency list rather than trying to optimize the matrix scan.

By following these practices—validating indices, handling symmetry and weights correctly, and selecting the representation based on density and workload—you can avoid the most common pitfalls and harness the full power of the adjacency matrix graph without incurring its potential downsides.

10. Interview Questions

Technical interviews frequently test understanding of graph representations, and the adjacency matrix graph is a common topic. Interviewers use it to assess your knowledge of trade-offs, complexity analysis, and ability to implement graph algorithms. Below are common questions with guidance on how to approach them.

Question 1: When would you prefer an adjacency matrix over an adjacency list?

This question tests your understanding of trade-offs. A strong answer should mention three scenarios: dense graphs where e is close to n^2, when the algorithm requires frequent O(1) edge existence checks (e.g., checking if a graph is complete), and when using matrix-based algorithms like Floyd-Warshall or computing transitive closure via matrix multiplication. Mention the O(n^2) space cost and O(n) neighbor iteration as downsides for sparse graphs. Conclude with the rule of thumb: matrix for dense/small graphs and fast edge queries, list for sparse/large graphs and efficient traversals.

Question 2: How do you check if a graph represented by an adjacency matrix is undirected?

The interviewer expects you to recognize the symmetry property. Explain that an undirected graph's adjacency matrix must be symmetric, i.e., matrix[i][j] == matrix[j][i] for all i, j. Provide an O(n^2) algorithm that iterates over the upper triangle and checks for symmetry, with early exit on mismatch. Discuss edge cases like self-loops on the diagonal. You can also mention that for a weighted undirected graph, the weights must also be symmetric.

Question 3: Given an adjacency matrix, how would you count the number of triangles in an undirected graph?

This is a more advanced question that connects the adjacency matrix to linear algebra. Explain two approaches. The brute-force approach is O(n^3): iterate over all triplets (i < j < k) and check if all three edges exist via O(1) lookups. The elegant matrix approach uses the trace of the cube of the adjacency matrix: number of triangles = trace(Adj^3) / 6. Explain why: (Adj^3)[i][i] counts closed walks of length 3 starting and ending at i, each triangle is counted 6 times (3 vertices * 2 directions). This demonstrates deeper insight and is highly valued in interviews for roles involving algorithms or data science.

Question 4: What is the time complexity of BFS and DFS using an adjacency matrix, and why?

Answer: Both BFS and DFS are O(n^2) when using an adjacency matrix. Reason: each vertex is visited once, and for each vertex, you must scan its entire row of n entries to find unvisited neighbors, leading to n * n operations. Contrast this with O(n + e) for an adjacency list, where you only iterate over actual neighbors. This question checks if you understand how the representation affects algorithm complexity, not just the abstract algorithm itself. Be prepared to write pseudocode for BFS/DFS with a matrix to illustrate the row scan.

Question 5: How would you represent a weighted graph with an adjacency matrix, and how do you handle absent edges?

Explain that you store the weight w at matrix[u][v] if an edge exists. For absent edges, you cannot use 0 if 0 is a valid weight, so you use a sentinel like infinity (math.inf) or None. Mention that the diagonal is typically 0 (distance to self is zero). Discuss how this representation directly supports algorithms like Dijkstra (with adjacency matrix, O(n^2) without a heap) and Floyd-Warshall, which initializes its distance matrix from the adjacency matrix. This shows practical implementation knowledge.

Preparing for these questions by implementing the adjacency matrix graph from scratch, analyzing its complexities, and practicing matrix-based graph problems will ensure you can confidently discuss and apply this fundamental data structure in any technical interview.