Graphs in Data Structures: Terminology and Representation in Python

A graph is a set of vertices (also called nodes) connected by edges. Graphs model anything made of connections: roads between cities, friendships, links between web pages, dependencies between tasks, or moves in a game. A tree is a special kind of graph with no cycles.

   A ─── B
   │   / │
   │  /  │
   C ─── D ─── E

Vocabulary#

We write V for the number of vertices and E for the number of edges. Graph algorithm costs are given in terms of both, like O(V + E).

Adjacency list#

The most common representation: for each vertex, a list of its neighbours. In Python, a dictionary of lists:

from collections import defaultdict

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)      # undirected: add both directions

for vertex in sorted(graph):
    print(vertex, "->", graph[vertex])
print("degree of D:", len(graph["D"]))

A -> ['B', 'C']
B -> ['A', 'C', 'D']
C -> ['A', 'B', 'D']
D -> ['B', 'C', 'E']
E -> ['D']
degree of D: 3

Space is O(V + E), and listing a vertex's neighbours costs O(its degree). This is the right choice for most real graphs, which are sparse (each vertex connects to only a few others).

Adjacency matrix#

A V × V grid where matrix[i][j] is 1 (or the weight) if there is an edge from vertex i to vertex j:

names = ["A", "B", "C", "D", "E"]
index = {name: i for i, name in enumerate(names)}
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

matrix = [[0] * len(names) for _ in names]
for u, v in edges:
    matrix[index[u]][index[v]] = 1
    matrix[index[v]][index[u]] = 1

print("   " + " ".join(names))
for name, row in zip(names, matrix):
    print(name, row)
print("B-D connected?", matrix[index["B"]][index["D"]] == 1)

   A B C D E
A [0, 1, 1, 0, 0]
B [1, 0, 1, 1, 0]
C [1, 1, 0, 1, 0]
D [0, 1, 1, 0, 1]
E [0, 0, 0, 1, 0]
B-D connected? True

Checking whether two specific vertices are connected is O(1), but the matrix always uses O(V²) space, even when there are few edges. It suits small or dense graphs.

Directed and weighted graphs#

For a weighted directed graph, store (neighbour, weight) pairs, and add each edge in one direction only:

roads = {
    "Home":   [("Market", 4), ("School", 2)],
    "School": [("Market", 1), ("Park", 7)],
    "Market": [("Park", 3)],
    "Park":   [],
}
for place, out in roads.items():
    for to, km in out:
        print(f"{place} -> {to}: {km} km")

in_degree = {p: 0 for p in roads}
for out in roads.values():
    for to, _ in out:
        in_degree[to] += 1
print(in_degree)

Home -> Market: 4 km
Home -> School: 2 km
School -> Market: 1 km
School -> Park: 7 km
Market -> Park: 3 km
{'Home': 0, 'School': 1, 'Market': 2, 'Park': 2}

Finding the cheapest route here is the job of Dijkstra's algorithm.

Edge list#

Sometimes a plain list of (u, v, weight) triples is enough. Algorithms that process edges in order of weight, like Kruskal's minimum spanning tree, use it directly.

Grids are graphs too#

A 2D grid is a graph where each cell is a vertex connected to its up, down, left and right neighbours. You usually do not build an adjacency list; you compute neighbours on the fly:

grid = [
    "..#",
    ".#.",
    "...",
]

def neighbours(r, c):
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] != "#":
            yield nr, nc

print(list(neighbours(0, 0)))
print(list(neighbours(2, 1)))

[(1, 0), (0, 1)]
[(2, 0), (2, 2)]

# cells are walls. Maze and map problems, and game pathfinding, work on graphs like this.

Which representation?#

Common mistakes#

Practice#

def reverse_graph(graph):
    reversed_g = {v: [] for v in graph}
    for u, neighbours in graph.items():
        for v in neighbours:
            reversed_g.setdefault(v, []).append(u)
    return reversed_g

follows = {"Asha": ["Ravi", "Meera"], "Ravi": ["Meera"], "Meera": [], "John": []}
print(reverse_graph(follows))

{'Asha': [], 'Ravi': ['Asha'], 'Meera': ['Asha', 'Ravi'], 'John': []}

Key takeaway#

Next: exploring a graph level by level, with Breadth-First Search (BFS).