Graphs

Lesson 6 of 7 in Recursion, Trees & Graphs · 45 min · Intermediate

Dots and lines: anything connected to anything.

Introduction

Your college lists six courses, and some say "take this one first". In what order can you take every course, and what if two of them each demand the other?

Trying orders by hand gets messy fast. Course 4 needs courses 1 and 2, course 5 needs 3 and 4, and soon you lose track of which courses are unlocked.

Now draw each course as a dot and each "first" rule as an arrow. Which dots could you take right now?

Lesson overview

This lesson will show you how to:

Explain how a graph is stored as one neighbour list per node.
Trace the indegree queue that orders the courses one free course at a time.
Spot a cycle when the ordering finishes with courses still left over.
Choose a graph, not a tree, when an item can have several parents.
Implement adjacency lists and the topological sort template from scratch.

The picture

A graph

Undirected graph with 5 nodes and 5 edges. Nodes: 0 (badge deg 2), 1 (badge deg 2), 2 (badge deg 2), 3 (badge deg 3, focus), 4 (badge deg 1). Edges: 0 and 1; 0 and 2; 1 and 3; 2 and 3; 3 and 4.

The same graph as lists: row i holds the neighbours of node i

Hash map with 5 buckets: bucket 0 1, 2; bucket 1 0, 3; bucket 2 0, 3; bucket 3 1, 2, 4; bucket 4 3. Marked: bucket 3 focus.

Mental model

Think of cities joined by roads. Some roads go both ways, some are one-way streets, and a few cost more to drive. Unlike a tree there is no top city: roads can loop back, and you can start anywhere.

A graph is things plus the links between them, and the usual way to store it is one list per node of the nodes it links to.

Words to know

node: One thing in the graph: a course, a city, a person. Also called a vertex. With n nodes we number them 0 to n - 1.
edge: A link between two nodes. In an undirected graph it works both ways. In a directed graph it is an arrow that goes one way only. Some graphs give each edge a weight, like minutes of driving.
degree: How many edges touch a node. In a directed graph, indegree counts the arrows pointing in and outdegree counts the arrows pointing out.
adjacency list: For each node, a list of its neighbours. It uses space for the nodes plus the edges, so it suits most problems. This is what we build in the first track.
adjacency matrix: An n by n table where cell [a][b] says whether an edge joins a and b. Checking one edge is instant, but the table always has n × n cells, even when there are only a few edges.
cycle: A path that leads from a node back to itself. Two courses that each need the other make a cycle.
DAG: A directed graph with no cycles (a directed acyclic graph). A "who goes first" order exists only for a DAG.
topological order: A line-up of a DAG's nodes where every arrow points forward: each node comes after everything it depends on.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: The problem is about things and the links between them: roads, friends, web pages, dependencies.
Yes: You get rules like "A must come before B" and need an order, or need to know whether one exists.
Yes: The input is a list of pairs [a, b]. Each pair is an edge.
Yes: You must say whether things are connected, or count separate groups of them.

Not this when

No: There is one top item and every other item has exactly one parent. That is a tree, which is simpler.
No: You only look things up by key. A hash map does that directly, with no links in sight.
No: Walking through the graph is the whole job, like fewest hops or counting islands. This lesson is about storing a graph and ordering it; the bfs-dfs lesson covers walking it.

Which pattern fits?

Which pattern? 1 of 5
There are 4 courses. A pair [1, 0] means take course 0 before course 1. Given a list of such pairs, return an order in which you can take every course, or report that it is impossible.
Which pattern? 2 of 5
Given a grid of 1s (land) and 0s (water), count the islands.
Which pattern? 3 of 5
Given a binary tree, return its maximum depth.
Which pattern? 4 of 5
In a town of n people, the judge is trusted by everybody else and trusts nobody. Given pairs [a, b] meaning a trusts b, find the judge or return -1.
Which pattern? 5 of 5
Count the ways to climb n stairs if you can take 1 or 2 steps at a time.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1indegree[v] = number of edges pointing into v, for every node v
2queue = every node with indegree 0, order = empty
while the queue is not empty:
3u = take the front of the queue, add u to order
for each neighbour v of u:
4indegree[v] = indegree[v] - 1
5if indegree[v] is 0: add v to the back of the queue
6if order holds all n nodes: return it, otherwise a cycle blocks the rest

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

from collections import deque


def topo_order(n, edges):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:
        adj[a].append(b)
        indegree[b] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []

Time · O(V + E)Space · O(V + E)

Every node enters the queue at most once and every edge is removed once, so the work is O(V + E), where V is the number of nodes and E the number of edges.
The O(V + E) space is the adjacency list. The indegree counts, the queue and the order add O(V) more.
A queue is the usual choice and gives the order in waves: first everything with no prerequisites, then what they unlocked. A stack would also give a valid order, only a different one.
The same check detects cycles: if fewer than n nodes come out, the rest are stuck behind a cycle. A depth-first search can do both jobs as well, and the bfs-dfs lesson covers walking a graph.
List or matrix? The adjacency list costs O(V + E) space and is the default. An adjacency matrix costs O(V²) cells but answers "is there an edge a-b?" in O(1), so it only pays off when the graph is small or packed with edges.
LeetCode writes a prerequisite as [a, b] meaning "take b first". That is the edge b to a, so flip the pair when you build the lists.
Weighted graphs store a cost on each edge. Counting hops no longer finds the cheapest route there; that needs Dijkstra's algorithm, which this course has not covered yet.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

There are numCourses courses labelled 0 to numCourses - 1. A pair [a, b] in prerequisites means you must take course b before course a. Return true if you can finish all courses.

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

false

Approach

Each pair [a, b] is the arrow b to a. Build the adjacency lists and count each course's indegree.
Queue every course with indegree 0, take one, lower the indegree of the courses it unlocks, and queue any that reach 0.
Here both courses have indegree 1, so the queue starts empty and nothing can be taken.
Count the courses taken. If it is fewer than numCourses, a cycle blocks the rest, so return false.

from collections import deque


def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, before in prerequisites:
        adj[before].append(course)
        indegree[course] += 1
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    taken = 0
    while queue:
        u = queue.popleft()
        taken += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return taken == num_courses

Time · O(V + E)Space · O(V + E)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

An undirected edge joins nodes 2 and 5. How do you store it in adjacency lists?
A graph has 1,000 nodes but only 1,500 edges. How do an adjacency list and an adjacency matrix compare?
In Kahn's algorithm, what does a node's indegree reaching 0 mean?
The queue runs empty, but only 3 of 5 nodes are in the order. What does that tell you?
Roads have different lengths (weights). Does the hop-counting walk of a queue find the quickest drive?

Question 1 of 5

An undirected edge joins nodes 2 and 5. How do you store it in adjacency lists?

Keep it in a separate list of edges and leave the node lists alone.Add 2 to the list of node 5 only.Add 5 to the list of node 2 and 2 to the list of node 5.Add 5 to the list of node 2 only.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

Solve Find if Path Exists in Graph (opens in a new tab) (LeetCode, easy)
Hint: Build the adjacency lists first. Then the question is whether you can walk from the source to the destination, which is what the bfs-dfs lesson teaches.
Solve Find the Town Judge (opens in a new tab) (LeetCode, easy)
Hint: The judge has indegree n - 1 and outdegree 0. Count both for every person, or keep one running balance.
Solve Number of Provinces (opens in a new tab) (LeetCode, medium)
Hint: The input is an adjacency matrix. Count the separate groups, where a group is everyone you can reach from one person.
Solve Is Graph Bipartite? (opens in a new tab) (LeetCode, medium)
Hint: Try to give every node one of two colours so that each edge joins different colours. An edge whose ends must share a colour breaks it.
Solve Find Eventual Safe States (opens in a new tab) (LeetCode, medium)
Hint: A node is safe when every path from it ends at a dead end. Reverse the edges and run Kahn-style from the nodes that have no outgoing edges.
Solve Course Schedule IV (opens in a new tab) (LeetCode, medium)
Hint: Each query asks whether one course leads to another, even through a chain. Think reachability, and let a topological order tell you what is known when.
Solve Network Delay Time (opens in a new tab) (LeetCode, medium)
Hint: Edges have weights, so counting hops is not enough. Settle the closest unsettled node, relax its roads, and the answer is the largest distance (or -1 if some node is never reached).
Solve Sort Items by Groups Respecting Dependencies (opens in a new tab) (LeetCode, hard)
Hint: Two topological sorts in one: order the groups, then order the items inside each group.

Additional resources

Graph theory (Wikipedia) (opens in a new tab) — Vertices, edges, directed and undirected graphs, and the vocabulary used throughout this lesson.
Topological sorting (Wikipedia) (opens in a new tab) — Defines topological orderings and explains why they exist for directed acyclic graphs.
Topological sort (cp-algorithms) (opens in a new tab) — Practical write-up of topological sorting, with code and notes on detecting cycles.
Graph data structures (VisuAlgo) (opens in a new tab) — Interactive animations of graph representations and traversals you can step through yourself.