Adjacency matrix

A matrix with 1 for an edge between two vertices.

An adjacency matrix stores the graph as a V×V matrix. If matrix[i][j] = 1 there is an edge from i to j; if 0 there is not.

Memory is O(V^2): suitable for dense graphs, wasteful for sparse ones. Neighbor query is O(1) and very fast.

In a weighted graph matrix[i][j] is the edge weight; 0 or infinity is used when there is no edge.

Comparison

The adjacency list uses less memory on sparse graphs (O(V+E)) and is efficient. The adjacency matrix suits dense graphs (O(V^2)).

With a matrix neighbor query is O(1); with a list O(degree). With a matrix scanning all neighbors is O(V); with a list O(degree), much faster.

The choice depends on the graph's density and the type of operation; it must be made carefully.

Write count_neighbors(graph, node). Return the node's neighbor count. Print 2 with g = {'a': ['b', 'c']}; print(count_neighbors(g, 'a')).

Show example solution

def count_neighbors(graph, node):
    # Count neighbors
    return len(graph[node])
g = {'a': ['b', 'c']}
print(count_neighbors(g, 'a'))