Graphs are everywhere—in social networks, navigation systems, and even in coding interviews! One of the most popular ways to represent graphs in programming is using an adjacency matrix. If you’re looking to dive into graph algorithms, understanding adjacency matrices is a critical first step.
This article breaks down adjacency matrices in simple terms, how they work, and how they’re used in common graph problems. By the end, you’ll know when and why to use them in your code.
What is an Adjacency Matrix?
Imagine you have a group of cities, and you want to represent the roads connecting them. An adjacency matrix is like a table where:
• Each row represents a city.
• Each column represents another city.
• The value at the intersection of a row and column tells you if there’s a road between those two cities.
How It Works
• If there’s a road, the value is 1.
• If there’s no road, the value is 0.
For a graph with n nodes (or cities), the adjacency matrix is an n times n table.
Example
Let’s say we have the following graph:
City A → City B → City C
↑ ↓
City D ← ← ← ← ← ← ← ← ←
The adjacency matrix would look like this:
A B C D
A 0 1 0 0
B 0 0 1 0
C 0 0 0 1
D 1 0 0 0
This matrix tells us:
• There’s a road from City A to City B (1 in row A, column B).
• There’s no road directly from City A to City C (0 in row A, column C).
Why Use an Adjacency Matrix?
Adjacency matrices are powerful because they’re simple and direct. They allow you to:
1. Quickly Check Connections:
• Need to know if City A is connected to City B? Just look up matrix[A][B].
2. Represent Dense Graphs:
• For graphs with many edges, adjacency matrices are memory-efficient.
3. Handle Weighted Graphs:
• Instead of 1 and 0, you can store the weight of an edge (like the distance between cities).
When NOT to Use an Adjacency Matrix
While adjacency matrices are great for dense graphs, they can be inefficient for sparse graphs (graphs with fewer edges). Why? They require O(n^2) space, even if most of the cells are 0. For sparse graphs, adjacency lists are a better choice.
Common Operations with Adjacency Matrices
1. Checking for an Edge
Want to know if there’s an edge between node i and node j ?
if (matrix[i][j] != 0) {
System.out.println("There's an edge!");
}
2. Adding an Edge
Adding a connection between two nodes is as simple as:
matrix[i][j] = 1; // Unweighted graph
matrix[i][j] = weight; // Weighted graph
3. Removing an Edge
To remove an edge, just set the value back to 0:
matrix[i][j] = 0;
Algorithms That Use Adjacency Matrices
Here’s how adjacency matrices are used in common graph algorithms:
Depth-First Search (DFS)
DFS explores a graph deeply along one path before backtracking. Using an adjacency matrix, you can visit neighbors easily:
void dfs(int[][] matrix, boolean[] visited, int node) {
visited[node] = true;
for (int neighbor = 0; neighbor < matrix.length; neighbor++) {
if (matrix[node][neighbor] == 1 && !visited[neighbor]) {
dfs(matrix, visited, neighbor);
}
}
}
- Loops through all possible neighbors of the current node using a matrix.
- Checks if there’s a connection between the current node and neighbor.
- If a neighbor is connected and not yet visited, the functon calls itself to explore that neighbor.
Breadth-First Search (BFS)
BFS explores a graph level by level. With an adjacency matrix, you check each neighbor at the current level:
void bfs(int[][] matrix, boolean[] visited, int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor = 0; neighbor < matrix.length; neighbor++) {
if (matrix[node][neighbor] == 1 && !visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
- Creates a Qureue to stores nodes that need to be processed during the BFS traversal.
- Adds the start node to the queue as the starting point.
- Updates the visited array for the start node to true.
- Continues processing nodes as long as the queue is not empty.
- Removes the front node from the queue for processing.
- Checks all neighbors of the current node.
Conclusion
Adjacency matrices are a simple yet powerful tool for representing graphs. While they might not be the best choice for sparse graphs, they shine in scenarios where quick edge lookups and dense connections are needed. By mastering adjacency matrices, you’ll be well-equipped to tackle many graph-related problems in competitive programming and real-world applications.
So next time you face a graph problem, consider whether an adjacency matrix is the right fit—it might just be the key to a clean and efficient solution!