Graphs & Representations

A graph is a set of things and the connections between them. Cities joined by roads, people who follow each other on social media, metro stations, web pages and their links, subjects and their prerequisites: all of these are graphs. Trees are a special kind of graph with no loops, but general graphs can connect anything to anything.

In this lesson you will learn the words used to describe graphs and the three standard ways to store one in code. Choosing the right representation decides how fast every graph algorithm in the next lessons will run.

Graph vocabulary

A graph has vertices (also called nodes) and edges that connect pairs of vertices. The number of vertices is written V and the number of edges E.

A directed graph with no cycles is called a DAG (directed acyclic graph), and it is important enough to get its own lesson: Topological Sort.

A graph is sparse when it has few edges compared with the maximum possible, and dense when it is close to the maximum. An undirected graph with V vertices can have at most V(V - 1)/2 edges. Road networks and social networks are sparse: a city connects to a handful of others, not to every city in the country.

Representation 1: edge list

The simplest form is a list of the edges themselves. It is how graphs often arrive in a file or an interview question. Here is a small road map between six cities, with example distances in km:

roads = [
    ("Delhi", "Rohtak", 70), ("Delhi", "Jaipur", 280), ("Delhi", "Agra", 230),
    ("Jaipur", "Agra", 240), ("Jaipur", "Ajmer", 135), ("Agra", "Gwalior", 120),
]

cities = sorted({c for u, v, _ in roads for c in (u, v)})
print("V =", len(cities), "E =", len(roads))
print(cities)

# Finding Jaipur's neighbours means scanning every edge: O(E)
print([v if u == "Jaipur" else u for u, v, _ in roads if "Jaipur" in (u, v)])

V = 6 E = 6
['Agra', 'Ajmer', 'Delhi', 'Gwalior', 'Jaipur', 'Rohtak']
['Delhi', 'Agra', 'Ajmer']

An edge list uses O(E) memory and is perfect for algorithms that just loop over all edges, such as Kruskal's algorithm in Minimum Spanning Trees & Union-Find. But asking "who are Jaipur's neighbours?" means scanning every edge, which is too slow for most algorithms.

Representation 2: adjacency matrix

An adjacency matrix is a V × V grid. Number the vertices 0 to V - 1; the cell matrix[i][j] holds the weight of the edge from i to j, or 0 (or infinity) if there is none. For an undirected graph, the matrix is symmetric: matrix[i][j] == matrix[j][i].

roads = [
    ("Delhi", "Rohtak", 70), ("Delhi", "Jaipur", 280), ("Delhi", "Agra", 230),
    ("Jaipur", "Agra", 240), ("Jaipur", "Ajmer", 135), ("Agra", "Gwalior", 120),
]
cities = ["Agra", "Ajmer", "Delhi", "Gwalior", "Jaipur", "Rohtak"]
index = {name: i for i, name in enumerate(cities)}

n = len(cities)
matrix = [[0] * n for _ in range(n)]
for u, v, km in roads:
    matrix[index[u]][index[v]] = km
    matrix[index[v]][index[u]] = km          # undirected: both directions

print(" " * 8 + "".join(f"{c[:6]:>7}" for c in cities))
for name, row in zip(cities, matrix):
    print(f"{name:>8}" + "".join(f"{x:>7}" for x in row))

print("Is there a road Agra-Jaipur?", matrix[index["Agra"]][index["Jaipur"]] > 0)

           Agra  Ajmer  Delhi Gwalio Jaipur Rohtak
    Agra      0      0    230    120    240      0
   Ajmer      0      0      0      0    135      0
   Delhi    230      0      0      0    280     70
 Gwalior    120      0      0      0      0      0
  Jaipur    240    135    280      0      0      0
  Rohtak      0      0     70      0      0      0
Is there a road Agra-Jaipur? True

Checking whether one particular edge exists is O(1), which is the matrix's strength. Its weakness is size: it always uses O(V²) memory, even if most cells are 0, and listing a vertex's neighbours means scanning a whole row, O(V). For India's roughly 7,000 railway stations, a matrix would need about 4.9 crore cells while the real track connections number only in the thousands. Use a matrix for small or dense graphs.

Representation 3: adjacency list

An adjacency list stores, for every vertex, a list of its neighbours. In Python, a dictionary of lists (or of dictionaries, for weights) is the natural choice. This is the representation you will use most.

from collections import defaultdict

roads = [
    ("Delhi", "Rohtak", 70), ("Delhi", "Jaipur", 280), ("Delhi", "Agra", 230),
    ("Jaipur", "Agra", 240), ("Jaipur", "Ajmer", 135), ("Agra", "Gwalior", 120),
]

graph = defaultdict(dict)                 # city -> {neighbour: km}
for u, v, km in roads:
    graph[u][v] = km
    graph[v][u] = km

print(graph["Jaipur"])                    # neighbours in O(1) to find
print("Agra-Jaipur road?", "Jaipur" in graph["Agra"], graph["Agra"]["Jaipur"], "km")

for city in sorted(graph, key=lambda c: -len(graph[c])):
    print(f"{city:8} degree {len(graph[city])}")

{'Delhi': 280, 'Agra': 240, 'Ajmer': 135}
Agra-Jaipur road? True 240 km
Delhi    degree 3
Jaipur   degree 3
Agra     degree 3
Rohtak   degree 1
Ajmer    degree 1
Gwalior  degree 1

An adjacency list uses O(V + E) memory, and looping over a vertex's neighbours costs only its degree. Because each neighbour collection here is a dict, checking one specific edge is also O(1) on average. For an unweighted graph, use a set or list of neighbours instead.

Directed graphs

In a directed graph, an edge from u to v does not imply one from v to u. Store only graph[u].add(v). The out-degree counts edges leaving a vertex; the in-degree counts edges arriving. On a social app, out-degree is "following" and in-degree is "followers".

from collections import defaultdict

follows = [("Priya", "Kabir"), ("Aarav", "Kabir"), ("Kabir", "Meera"),
           ("Meera", "Priya"), ("Isha", "Kabir"), ("Priya", "Meera")]

following = defaultdict(set)
followers = defaultdict(set)
for u, v in follows:
    following[u].add(v)
    followers[v].add(u)

people = sorted({p for edge in follows for p in edge})
for p in people:
    print(f"{p:6} follows {len(following[p])}, followed by {len(followers[p])}")

print("Does Kabir follow Priya?", "Priya" in following["Kabir"])

Aarav  follows 1, followed by 0
Isha   follows 1, followed by 0
Kabir  follows 1, followed by 3
Meera  follows 1, followed by 2
Priya  follows 2, followed by 1
Does Kabir follow Priya? False

Storing the reversed graph (followers) as well as the forward graph is a common trick when an algorithm needs to walk edges backwards.

Graphs you do not store: grids

Many problems hide a graph inside a grid: a maze, a city map or a game board. Each open cell is a vertex, and it has edges to the open cells above, below, left and right. You do not build an adjacency list at all; you compute the neighbours when you need them.

city_map = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    "...#...E",
]

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(city_map) and 0 <= nc < len(city_map[0]) \
                and city_map[nr][nc] != "#":
            yield nr, nc

print(list(neighbours(0, 0)))
print(list(neighbours(2, 2)))
open_cells = sum(row.count(".") + row.count("S") + row.count("E") for row in city_map)
print("vertices:", open_cells)

[(1, 0), (0, 1)]
[(1, 2), (3, 2), (2, 3)]
vertices: 24

The 0 <= checks keep you inside the grid, and the "#" check skips blocked cells. In Breadth-First Search (BFS) you will find the shortest path from S to E on this exact map.

Common mistakes

• Adding only one direction for an undirected edge. Add both graph[u][v] and graph[v][u].
• Forgetting vertices with no edges. An isolated vertex never appears in an edge list; add it to the adjacency list explicitly if it matters.
• Using a matrix for a large sparse graph. O(V²) memory runs out quickly.
• Using a list of neighbours and then checking v in graph[u] often. That is O(degree); use a set.

Key points

• A graph has vertices and edges; edges can be directed or undirected, weighted or unweighted.
• An edge list is simple and O(E) in memory, but slow for finding neighbours.
• An adjacency matrix gives O(1) edge checks but always uses O(V²) memory.
• An adjacency list (a dict of sets or dicts in Python) uses O(V + E) memory and is the default choice.
• Directed graphs have in-degree and out-degree; grids are graphs whose neighbours you compute on the fly.

from collections import defaultdict

prereqs = [("Maths I", "Maths II"), ("Maths II", "DSA"), ("Programming", "DSA"),
           ("DSA", "Algorithms"), ("Programming", "OOP")]

graph = defaultdict(list)
in_degree = defaultdict(int)
for before, after in prereqs:
    graph[before].append(after)
    in_degree[after] += 1
    in_degree[before] += 0          # make sure every subject appears

for subject in sorted(in_degree):
    print(f"{subject:12} in-degree {in_degree[subject]}")

Algorithms   in-degree 1
DSA          in-degree 2
Maths I      in-degree 0
Maths II     in-degree 1
OOP          in-degree 1
Programming  in-degree 0