Graphs

Graphs | Algoryva

First, the naive way

An n × n table for every graph

The first idea many people have is a table with one row and one column per vertex, and a 1 in cell (a, b) when a and b are joined. It is called an adjacency matrix, and it makes “is there an edge between a and b?” instant.

But the table has n × n cells no matter how few edges exist. A road network with 100,000 junctions has about 10 billion cells, almost all zero, and only a few hundred thousand real roads.

python

def build_matrix(n, edges):
    m = [[0] * n for _ in range(n)]
    for a, b in edges:
        m[a][b] = 1
        m[b][a] = 1
    return m

m = build_matrix(4, [(0, 1), (1, 2), (1, 3)])
print(m[1])   # [1, 0, 1, 1]
print(sum(map(sum, m)) // 2)   # 3

Cost: O(V²) memory and O(V) just to list one vertex's neighbours. Fine for V up to about 2,000; impossible for V = 10⁵.

Worked by hand

Three representations of the same graph

Vertices 0 to 3, undirected edges: 0–1, 1–2, 1–3.

representation	contents	memory
edge list	(0,1) (1,2) (1,3)	O(E)
adjacency matrix	row 0: 0 1 0 0 · row 1: 1 0 1 1 · row 2: 0 1 0 0 · row 3: 0 1 0 0	O(V²)
adjacency list	0: [1] · 1: [0, 2, 3] · 2: [1] · 3: [1]	O(V + E)

1
Degrees at a glance
Vertex 1 has degree 3 (the length of its list); vertices 0, 2 and 3 have degree 1. The degrees add up to 6, which is twice the number of edges: every undirected edge is counted at both ends.
2
Which to use
Edge list: when you only iterate over all edges (Kruskal, Union-Find). Adjacency list: for traversals and almost everything else. Adjacency matrix: only when V is small and you need instant edge lookups or the graph is dense.

Implementation

Building adjacency lists from input

Contest input usually gives n vertices and m edges, one pair per line. The only decisions are whether to add the reverse edge and whether to store a weight.

python

def build_undirected(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    return g

def build_directed(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
    return g

def build_weighted(n, edges):
    g = [[] for _ in range(n)]
    for a, b, w in edges:
        g[a].append((b, w))
        g[b].append((a, w))
    return g

print(build_undirected(4, [(0, 1), (1, 2), (1, 3)]))   # [[1], [0, 2, 3], [1], [1]]
print(build_directed(3, [(0, 1), (1, 2), (0, 2)]))   # [[1, 2], [2], []]
print(build_weighted(3, [(0, 1, 5), (1, 2, 2)]))   # [[(1, 5)], [(0, 5), (2, 2)], [(1, 2)]]

Reading the code

›[[] for _ in range(n)] gives each vertex its own empty list. [[]] * n would make all vertices share one list (the aliasing trap from the Arrays lesson).
›For an undirected graph every edge is stored twice, once at each end. For a directed graph only once, in the direction of the arrow.
›For weights, store (neighbour, weight) pairs so one loop gives both.
›If the input numbers vertices from 1, either allocate n + 1 lists and ignore index 0, or subtract 1 as you read.

Implementation

Asking simple questions of a graph

Once the graph is built, many questions are one loop away.

python

def build_undirected(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    return g

g = build_undirected(5, [(0, 1), (1, 2), (1, 3), (3, 4)])

degrees = [len(nb) for nb in g]
print(degrees)   # [1, 3, 1, 2, 1]
print(sum(degrees) == 2 * 4)   # True
print(max(range(5), key=lambda v: degrees[v]))   # 1
print([v for v in range(5) if len(g[v]) == 1])   # [0, 2, 4]
print(4 in g[3])   # True

Reading the code

›len(g[v]) is the degree of v: no counting loop needed.
›The sum of all degrees is always twice the number of edges (the *handshake* rule), a handy sanity check on your input.
›Degree-1 vertices are the leaves of a tree-like graph.
›4 in g[3] checks for an edge by scanning one list: O(degree), not O(1). If you need many edge lookups on a dense graph, add a set of pairs or use a matrix.

Worked problem

Find the town judge

The problem

In a town of n people numbered 1 to n, a pair [a, b] means person a trusts person b. If a judge exists, the judge trusts nobody and everyone else trusts the judge. Return the judge's number, or -1 if there is none.

Translate to a directed graph: an edge a → b for each trust pair.
The judge has out-degree 0 (trusts nobody) and in-degree n − 1 (trusted by everyone else).
Count both degrees in one pass over the edges, then look for a person with those numbers.

python

def find_judge(n, trust):
    out_deg = [0] * (n + 1)
    in_deg = [0] * (n + 1)
    for a, b in trust:
        out_deg[a] += 1
        in_deg[b] += 1
    for p in range(1, n + 1):
        if out_deg[p] == 0 and in_deg[p] == n - 1:
            return p
    return -1

print(find_judge(3, [[1, 3], [2, 3]]))   # 3
print(find_judge(3, [[1, 3], [2, 3], [3, 1]]))   # -1

Takeaway. Some graph problems never need a traversal: the answer is a property of the degrees. Here no adjacency list is even built. Always ask whether counting is enough before reaching for BFS or DFS.

Worked problem

Is this graph a tree?

The problem

Given n vertices (numbered 0 to n − 1) and a list of undirected edges, decide whether the graph is a tree: connected, with no cycles.

A tree on n vertices has exactly n − 1 edges, so any other edge count is an immediate No.
With exactly n − 1 edges, the graph is a tree if and only if it is connected (a connected graph with n − 1 edges cannot contain a cycle).
Check connectivity with a traversal from vertex 0 and count the vertices reached.

python

def is_tree(n, edges):
    if len(edges) != n - 1:
        return False
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    seen = {0}
    stack = [0]
    while stack:
        u = stack.pop()
        for v in g[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return len(seen) == n

print(is_tree(4, [(0, 1), (1, 2), (2, 3)]))   # True
print(is_tree(4, [(0, 1), (1, 2), (2, 0)]))   # False
print(is_tree(1, []))   # True

Takeaway. Combining a counting fact (edges = n − 1) with one connectivity check replaces a full cycle search. The second example has 3 edges, the right count, but contains a cycle and leaves vertex 3 unreachable, so the traversal reaches only 3 of 4 vertices.

Wrap-up

Remember this

A graph is vertices plus edges, and it models any set of things with relationships.
Edges may be directed or undirected, weighted or not; degree counts edges at a vertex.
Use an adjacency list for almost everything: O(V + E) memory and cheap neighbour loops. A matrix is only for small, dense graphs.
Build lists with [[] for _ in range(n)], and add both directions for undirected edges.
Grids, puzzles and dependency lists are graphs in disguise; some questions are answered by degrees alone.

Cheat sheet

Adjacency list: g = [[] for _ in range(n)]; g[a].append(b) (+ g[b].append(a) if undirected)
Weighted: g[a].append((b, w))
Degree: len(g[v]); sum of degrees = 2 × edges (undirected)
Memory: list O(V + E) · matrix O(V²) · edge list O(E)
Tree: connected, no cycles, exactly n − 1 edges
Hidden graphs: pairs, grids, states with moves

Top traps to avoid

Using [[]] * n for the adjacency list.
Adding an undirected edge in one direction only.
Choosing an adjacency matrix for a large sparse graph.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why is an adjacency list usually preferred over an adjacency matrix?
2.For an undirected graph with 6 edges, what is the sum of all vertex degrees?
3.What goes wrong with g = [[]] * n as an adjacency list?
4.“Given prerequisites like (course a requires course b), can all courses be completed?” is best modelled as:
5.A graph has 100,000 vertices and 200,000 edges. Which representation is practical?
6.A tree has 10 vertices. How many edges does it have?
7.Edges [(1,2),(1,3),(2,3)] in an undirected graph. What is the degree of node 1?
8.How many edges does the complete graph on 4 nodes have?
9.Which representation uses O(n + m) memory?
10.In an adjacency matrix, how long does it take to test whether edge (u, v) exists?
11.What does cycle detection in an undirected graph need, to avoid false alarms?
12.Nodes 1 to 4 with edges (1,2) and (3,4). How many connected components are there? (union-find with path lookup.)
13.A BFS or DFS over a graph with n nodes and m edges: what is the time?
14.How many edges does a tree with 5 nodes have?
15.Why is an adjacency list preferred for sparse graphs?

Graphs

After this lesson you will be able to

Builds on

Unlocks

A subway map

Vocabulary

An n × n table for every graph

Store only the connections that exist

A graph being explored

Three representations of the same graph

Building adjacency lists from input

Reading the code

Asking simple questions of a graph

Reading the code

Trade-offs between the representations

Edge cases

Mistakes to avoid

How to spot a hidden graph

Find the town judge

Is this graph a tree?

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core12 problems

Application46 problems

Challenge2 problems