Adjacency Matrix: Another Representation Method for Graphs and a Comparison of Advantages and Disadvantages

In data structures, a graph is a data structure composed of vertices and edges. There are many ways to represent graphs, such as adjacency lists, adjacency matrices, etc. Among them, the adjacency matrix is an intuitive and fundamental representation method, especially suitable for beginners to understand.

一、What is an Adjacency Matrix?¶

An adjacency matrix is essentially a two-dimensional array used to represent the connection relationships between vertices in a graph. Its core idea is: using the rows and columns of the matrix to correspond to the vertices of the graph, and the element values in the matrix represent whether there is an edge between two vertices and the weight of the edge (if weighted).

1. Basic Definition¶

Assume a graph has n vertices, numbered 0, 1, 2, ..., n-1. The adjacency matrix is an n×n two-dimensional array adj, where:
- If adj[i][j] = 1 (or a specific weight value), it means there is an edge between vertex i and vertex j;
- If adj[i][j] = 0 (or infinity ∞), it means there is no edge between vertex i and vertex j (for weighted graphs, ∞ indicates no direct edge).

2. Example: Adjacency Matrix of an Undirected Graph¶

Suppose there is an undirected graph with vertices A, B, C, D (numbered 0, 1, 2, 3), and edges A-B, B-C, C-D, D-A. Its adjacency matrix is as follows:

	A(0)	B(1)	C(2)	D(3)
A(0)	0	1	0	1
B(1)	1	0	1	0
C(2)	0	1	0	1
D(3)	1	0	1	0

For example: adj[0][1] = 1 indicates there is an edge between vertex A and B; adj[0][2] = 0 indicates there is no edge between A and C.

二、Advantages of Adjacency Matrix¶

Quickly Check if an Edge Exists
To check if there is an edge between vertices i and j, simply access adj[i][j], with a time complexity of O(1). For example, in an adjacency list, you may need to traverse a linked list to find, but the adjacency matrix does not require traversal and directly locates via index.
Efficiently Calculate Vertex Degree
- Undirected Graph: The degree of vertex i (number of edges connected to other vertices) is the sum of the elements in the i-th row of the adjacency matrix (since in an undirected graph, the edge (i,j) appears in both the i-th row and j-th column).
- Directed Graph: The out-degree of vertex i (number of edges starting from i) is the sum of the i-th row, and the in-degree (number of edges pointing to i) is the sum of the i-th column.
Suitable for Dense Graphs
If the graph has many edges (close to n², i.e., the square of the number of vertices), the adjacency matrix has high space utilization. For example, a complete graph (every two vertices have an edge) will be completely filled in the adjacency matrix; in this case, the adjacency list may waste space due to extra storage.
Simple Implementation
For beginners, the array structure of the adjacency matrix is intuitive and easy to understand, requiring no complex data structures (such as linked lists or pointers), making it easy to understand and code.

三、Disadvantages of Adjacency Matrix¶

Low Space Efficiency
The adjacency matrix requires n×n space. For sparse graphs (graphs with far fewer edges than n²), it causes a large amount of space waste. For example, a graph with 1000 vertices and only 100 edges will require 1000×1000 = 1000000 elements in the adjacency matrix, while the adjacency list only needs to store 100 edge information, showing a significant space advantage.
Low Efficiency in Traversing Adjacent Vertices
To traverse all adjacent vertices of vertex i, you need to iterate through the i-th row (or column) of the adjacency matrix, with a time complexity of O(n). For example, if vertex A has 4 adjacent vertices, the adjacency matrix requires iterating through 4 vertices to find all neighbors, while the adjacency list only requires directly accessing the linked list, with a time complexity of O(degree) (degree is usually much smaller than n).
Not Suitable for Dynamic Edge Count Adjustment
When the number of edges in the graph changes frequently (e.g., inserting or deleting edges), the adjacency matrix requires modifying array elements. Although modifying a single element is O(1), the overall efficiency for large-scale graph dynamic operations is still less flexible than the adjacency list.

四、Summary¶

The core feature of the adjacency matrix is trading space for time:
- Suitable Scenarios: Dense graphs (many edges), scenarios requiring frequent edge existence queries, or calculating vertex degrees.
- Not Suitable Scenarios: Sparse graphs (few edges), scenarios requiring frequent traversal of adjacent vertices.

For beginners, the adjacency matrix is a fundamental tool to understand graphs, allowing quick mastery of basic connection relationships. However, in practical applications, choose the appropriate representation method based on the graph type (dense/sparse).