Adjacency Matrix vs Adjacency List: Key Differences and Usage

An adjacency matrix uses a 2D array to represent graph connections, making it fast to check if an edge exists but using more memory. An adjacency list stores neighbors for each node in lists, saving space especially for sparse graphs but making edge checks slower.

Quick Comparison

This table summarizes the main differences between adjacency matrix and adjacency list representations of graphs.

Factor	Adjacency Matrix	Adjacency List
Storage	Uses a 2D array of size V×V (V = number of vertices)	Uses an array of lists, each list stores neighbors of a vertex
Memory Usage	High, always uses V×V space	Low, proportional to V + E (E = number of edges)
Edge Check	O(1) time to check if edge exists	O(k) time, where k is neighbors count
Adding Edge	O(1) time	O(1) time (append to list)
Suitable For	Dense graphs with many edges	Sparse graphs with fewer edges
Iteration Over Neighbors	O(V) time, checks all vertices	O(k) time, only actual neighbors

Key Differences

An adjacency matrix represents a graph as a square grid where each cell at row i and column j indicates if there is an edge from vertex i to vertex j. This makes it very fast to check if two vertices are connected because you just look up one cell. However, it always uses memory for all possible edges, even if many don't exist, which can be wasteful for graphs with few edges.

In contrast, an adjacency list stores only the neighbors of each vertex in a list or similar structure. This saves memory because it only keeps track of existing edges. But checking if an edge exists between two vertices requires searching through the list, which can be slower if a vertex has many neighbors.

Overall, adjacency matrices are simple and fast for dense graphs, while adjacency lists are more memory-efficient and better for sparse graphs.

Code Comparison

Here is how to represent a graph and check for an edge using an adjacency matrix in Python.

python

class GraphMatrix:
    def __init__(self, vertices):
        self.V = vertices
        self.matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1  # For undirected graph

    def has_edge(self, u, v):
        return self.matrix[u][v] == 1

# Example usage
graph = GraphMatrix(4)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.has_edge(0, 1))  # True
print(graph.has_edge(0, 3))  # False

Output

True
False

Adjacency List Equivalent

Here is the equivalent graph representation and edge check using an adjacency list in Python.

python

class GraphList:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # For undirected graph

    def has_edge(self, u, v):
        return v in self.adj[u]

# Example usage
graph = GraphList(4)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.has_edge(0, 1))  # True
print(graph.has_edge(0, 3))  # False

Output

True
False

When to Use Which

Choose an adjacency matrix when your graph is dense, meaning it has many edges close to the maximum possible. This is because the matrix allows quick edge checks and simple implementation, and the memory cost is acceptable.

Choose an adjacency list when your graph is sparse, with relatively few edges. It uses much less memory and is more efficient for iterating over neighbors. However, edge existence checks are slower compared to a matrix.

In summary, use adjacency matrix for speed in dense graphs and adjacency list for memory efficiency in sparse graphs.

Key Takeaways

Adjacency matrix uses more memory but allows O(1) edge checks.

Adjacency list saves memory and is better for sparse graphs.

Use adjacency matrix for dense graphs with many edges.

Use adjacency list for sparse graphs with fewer edges.

Edge existence is faster in adjacency matrix, neighbor iteration is faster in adjacency list.