🎓 A1Learner
🔍

DSA Representing a Graph

An adjacency list stores each vertex with the list of its neighbours. An adjacency matrix stores a grid that marks 1 where an edge joins two vertices and 0 where none does.

Building an adjacency list

Each edge is added at both ends. The neighbour lists are sorted so the result is stable.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in sorted(graph):
    print(name, sorted(graph[name]))

Building an adjacency matrix

The names fix the row and column order. A cell is 1 only where an edge joins the pair.

names = ["A", "B", "C", "D"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
pos = {name: i for i, name in enumerate(names)}
matrix = [[0] * 4 for _ in range(4)]
for a, b in edges:
    matrix[pos[a]][pos[b]] = 1
    matrix[pos[b]][pos[a]] = 1
for row in matrix:
    print(row)

Reading neighbours from the list

One dict lookup gives every neighbour of a vertex. The list for B holds exactly its two neighbours.

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
print(graph["B"])
print(len(graph["B"]))

Example

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
names = ["A", "B", "C", "D"]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in names:
    graph[name] = sorted(graph[name])
print("Adjacency list:")
for name in names:
    print(name, graph[name])
pos = {name: i for i, name in enumerate(names)}
matrix = [[0] * len(names) for _ in range(len(names))]
for a, b in edges:
    matrix[pos[a]][pos[b]] = 1
    matrix[pos[b]][pos[a]] = 1
print("Adjacency matrix:")
for row in matrix:
    print(row)
stored = sum(len(graph[name]) for name in names)
cells = len(names) * len(names)
print("List entries:", stored)
print("Matrix cells:", cells)
print("Neighbours of C:", graph["C"])

Key points

  • Adjacency list: a dict that maps each vertex to its list of neighbours
  • Adjacency matrix: a grid with one row and one column per vertex
  • A matrix cell holds 1 when an edge joins the row vertex to the column vertex
  • A neighbour lookup in a list reads one entry of the dict
  • An undirected edge appears twice in an adjacency list, once at each end
  • A list stores only the edges that exist.

In this example, one edge list builds both forms of the same graph. The adjacency list gives each vertex its sorted neighbours. The matrix marks 1 in both directions for each undirected edge. The list holds eight entries because each of the four edges appears twice. The matrix holds sixteen cells because four vertices make a four by four grid. The last line reads the neighbours of C from the list with one lookup.

Note

A matrix stores a cell for every pair of vertices.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A graph has 5 vertices. How many cells does its adjacency matrix hold?