Adjacency Matrix Representation in C++

The Concept of an Adjacency Matrix

At its core, a graph is a collection of vertices and the edges that connect them. An adjacency matrix is a straightforward way to encode this information. For a graph with $V$ vertices (let's say they are numbered from 0 to $V-1$), we can create a $V\times V$ square matrix.

Let's call this matrix adj. The rule is simple:

• adj[i][j] contains a value indicating the nature of the edge from vertex i to vertex j.

For a simple, unweighted graph, this value is typically a boolean (0 or 1):

• adj[i][j] = 1 if an edge exists from i to j.
• adj[i][j] = 0 if no edge exists from i to j.

To see this in action, take a look at the helpful summary image below. Focus on the top-left (Undirected Unweighted) and bottom-left (Directed Unweighted) examples.

Notice two key properties visible in the "Graph Representation" image:

1. Undirected Graphs: The adjacency matrix for an undirected graph is always symmetric. If there is an edge between 0 and 1, then adj[0][1] = 1 and adj[1][0] = 1. The matrix is a mirror image across its main diagonal (from top-left to bottom-right).
2. Directed Graphs: The matrix is not necessarily symmetric. An edge from 0 to 1 means adj[0][1] = 1, but this tells us nothing about adj[1][0]. A 0 there would mean the edge is one-way.

Implementation in C++

Now, let's translate this concept into code. In competitive programming, graph problems typically provide input in a standard format. A very popular format, which you'll see on platforms like Codeforces and AtCoder, is to first give you the number of vertices $N$ and the number of edges $M$, followed by $M$ lines, each describing one edge.

The take U forward video provides an excellent explanation of this common input structure and how to begin building a representation from it.

With that conceptual understanding, let's look at a practical C++ implementation. In C++, we typically use a vector<vector<int>> to create a dynamic 2D array for our matrix.

The following reading provides a concise, competitive-programming-focused code snippet for building an adjacency matrix from standard input.

As you see in the code, after reading the number of vertices n and edges m, you initialize an n x n matrix (or (n+1) x (n+1) for 1-based indexing) with zeros. Then, you loop m times. In each iteration, you read a pair of vertices u and v that form an edge and set adj[u][v] = 1. For an undirected graph, you also set adj[v][u] = 1 to maintain symmetry.

Representing Weighted Graphs

The adjacency matrix concept extends naturally to weighted graphs. Instead of storing a 1 to indicate an edge's existence, you store the edge's weight.

What if there is no edge between two vertices? We need a special value to signify this. Using 0 is risky, as an edge could legitimately have a weight of 0. A common practice in competitive programming is to initialize the matrix with a very large value, representing infinity (INF). The distance from a node to itself, adj[i][i], is always 0.

This approach is detailed in the next section of the same article.

Analysis: Strengths and Weaknesses

Choosing the right data structure is about understanding trade-offs. The adjacency matrix has clear advantages and disadvantages that you must consider.

Space Complexity:
The most significant drawback of the adjacency matrix is its space requirement. For a graph with $V$ vertices, it always consumes $O(V^2)$ memory, regardless of how many edges the graph has. If $V=10^5$, a $V\times V$ matrix would require approximately $(10^5{)}^2\times 4$ bytes = 40 GB of memory, which is far beyond the typical memory limits (256-512 MB) in programming contests.
Therefore, an adjacency matrix is only feasible for dense graphs (where the number of edges $E$ is close to $V^2$) or when $V$ is small (e.g., $V\le 2000$).

The take U forward video makes this point very clearly.

Time Complexity:
The adjacency matrix shines in one key operation: checking for an edge.

• Check for an edge (u, v): This is an $O(1)$ operation. You can simply access adj[u][v] and see if it's non-zero (or not INF for weighted graphs).
• Iterate through all neighbors of a vertex u: This is an $O(V)$ operation. To find all vertices connected to u, you must traverse the entire u-th row of the matrix. This is inefficient for sparse graphs (where $E$ is much smaller than $V^2$), as you might scan many zeros to find just a few neighbors.

The table in the resource Graph Input Methods summarizes this trade-off. We will revisit this table in a future lesson, but for now, focus on the first row.

Conclusion

In this lesson, you have learned how to translate the abstract idea of a graph into a concrete C++ data structure: the adjacency matrix. We have seen how this simple 2D array can represent directed, undirected, weighted, and unweighted graphs.

Key Takeaways:

• An adjacency matrix is a $V\times V$ grid where adj[i][j] stores information about the edge from vertex i to vertex j.
• In C++, this is typically implemented with vector<vector<int>>.
• Undirected graphs produce a symmetric matrix, while directed graphs may not.
• Weighted graphs store edge weights in the matrix, using an "infinity" value to represent the absence of an edge.
• The primary strength of the adjacency matrix is its $O(1)$ time complexity for checking the existence of an edge.
• Its primary weakness is its $O(V^2)$ space complexity, which makes it unsuitable for graphs with a large number of vertices.

This final point about space complexity is critical. For many problems in competitive programming where the number of vertices is large but the number of edges is relatively small (a sparse graph), the adjacency matrix is not a viable option. This motivates the need for our next topic: the adjacency list, a more memory-efficient way to represent graphs, which we will cover in the next lesson.