What is an adjacency matrix?
An adjacency matrix is a way to represent a graph as a square table (matrix), where rows and columns correspond to vertices, and the cell values show whether there is an edge between them.
Definition
For a graph with vertices ( V = {v_1, v_2, ..., v_n} ):
the adjacency matrix is a matrix ( A[n][n] ), where
[
A[i][j] =
\begin{cases}
1, & \text{if there is an edge from } v_i \text{ to } v_j,
0, & \text{if there is no edge.}
\end{cases}
]
If the graph is weighted, the cell stores the edge weight instead of 1 and 0.
Example (undirected graph)
Edges: A-B, A-C, B-C
A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]The matrix is symmetric about the diagonal (A-B = B-A).
Example (directed graph)
Edges: A→B, B→C
A B C
A [ 0 1 0 ]
B [ 0 0 1 ]
C [ 0 0 0 ]Features
- The matrix size is always n × n, where n is the number of vertices.
- A[i][j] = 1 - there is a connection, A[i][j] = 0 - there is none.
- In directed graphs, the matrix is not symmetric.
- A loop (an edge from a vertex to itself) is shown on the diagonal.
Summary: an adjacency matrix is a table where, from the coordinates of two vertices, you can instantly find out whether there is an edge between them (and what its weight is).
Short Answer
Interview readyA concise answer to help you respond confidently on this topic during an interview.