What is Adjacency Matrix: Definition, Example, and Uses

An adjacency matrix is a way to represent a graph using a square grid (matrix) where each cell shows if there is a connection between two nodes. It uses rows and columns to represent nodes, and the value in each cell indicates whether an edge exists between those nodes.

How It Works

Imagine you have a group of friends, and you want to show who is friends with whom using a table. Each friend is listed both across the top (columns) and down the side (rows) of the table. If two friends know each other, you put a mark (like 1) in the cell where their row and column meet; if not, you put a 0.

This table is exactly how an adjacency matrix works for a graph. Each node (or point) in the graph is represented by a row and a column. The value inside the matrix cell tells you if there is a direct link (edge) between those two nodes. For example, a 1 means connected, and a 0 means no connection.

This method is simple and fast to check if two nodes are connected, but it can use a lot of space if the graph has many nodes with few connections.

Example

This example shows how to create and print an adjacency matrix for a simple graph with 4 nodes.

python

def print_adjacency_matrix(matrix):
    for row in matrix:
        print(' '.join(str(cell) for cell in row))

# Graph with 4 nodes (0 to 3)
# Edges: 0-1, 0-2, 1-2, 2-3
adj_matrix = [
    [0, 1, 1, 0],  # Connections for node 0
    [1, 0, 1, 0],  # Connections for node 1
    [1, 1, 0, 1],  # Connections for node 2
    [0, 0, 1, 0]   # Connections for node 3
]

print_adjacency_matrix(adj_matrix)

Output

0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

When to Use

Use an adjacency matrix when you need to quickly check if two nodes are connected, especially in graphs with a small number of nodes or dense connections. It is useful in algorithms that require fast edge lookups, like some shortest path or network flow algorithms.

However, if the graph is very large and has few edges (sparse), an adjacency matrix can waste memory. In such cases, other representations like adjacency lists are better.

Real-world examples include social networks (small groups), computer networks, and game maps where quick connection checks are important.

Key Points

• An adjacency matrix is a square grid representing connections between nodes.
• Each cell shows if an edge exists between two nodes (1 for yes, 0 for no).
• It allows fast checks for connections but can use a lot of memory for large sparse graphs.
• Best for small or dense graphs where quick edge lookup is needed.

Key Takeaways

An adjacency matrix uses a square grid to show connections between graph nodes.

It provides quick checks for edges but can be memory-heavy for large sparse graphs.

Ideal for small or dense graphs where fast edge lookup is important.

Each cell value indicates if two nodes are directly connected (1) or not (0).