Unit 26: Graphs
Maps, friends and finding paths.
Unit 26 of 31 in Python for kids. Its 5 lessons are Dots and Lines, Spreading Out, Going Deep, Finding a Way Through and Graph Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🕸️ Dots and Lines
When a tree is not enough
A tree branches downwards and never joins back up. A graph lets anything connect to anything — towns joined by roads, people who know each other, web pages that link. The dots are nodes and the lines are edges.
Python
roads = {
"home": ["shop", "park"],
"shop": ["home"],
"park": ["home"],
}
print(roads["home"])
print(len(roads))It prints
['shop', 'park'] 3
Both ways, or only one
If the connection goes both ways, put each in the other's list. A one-way graph (like following someone online) only lists it once.
Python
friends = {
"Ada": ["Sam"],
"Sam": ["Ada"],
}
print("Sam" in friends["Ada"])
print("Ada" in friends["Sam"])It prints
True True
Counting connections
How many edges a node has is its degree — how busy that place is.
Python
graph = {
"a": ["b", "c"],
"b": ["a"],
"c": ["a"],
}
for node in graph:
print(node, len(graph[node]))It prints
a 2 b 1 c 1
Try it yourself
What is an edge?
- The outside of the graph
- A connection between two nodes
- The last node
- A value stored in a node
What does this print?
Python
g = {"x": ["y", "z"], "y": [], "z": ["y"]}
print(len(g["x"]))
print(g["y"])Answer them in the app
🌊 Spreading Out
Visiting everything, nearest first
Breadth-first search spreads out like a ripple: all the places one step away, then all those two steps away. It uses a queue — which is why you met one in unit 21.
Python
from collections import deque
graph = {
"a": ["b", "c"],
"b": ["d"],
"c": [],
"d": [],
}
def bfs(start):
seen = [start]
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for neighbour in graph[node]:
if neighbour not in seen:
seen.append(neighbour)
queue.append(neighbour)
bfs("a")It prints
a b c d
Why you must remember where you have been
Graphs can loop back on themselves. Without the seen list you would go round for ever — this is the bug everyone writes once.
Python
graph = {"a": ["b"], "b": ["a"]}
seen = []
queue = ["a"]
steps = 0
while queue and steps < 10:
node = queue.pop(0)
if node in seen:
continue
seen.append(node)
for n in graph[node]:
queue.append(n)
steps = steps + 1
print(seen)It prints
['a', 'b']
Counting how far away things are
Because BFS reaches everything by the shortest route first, you can record the distance as you go.
Python
from collections import deque
graph = {"a": ["b"], "b": ["c"], "c": []}
distance = {"a": 0}
queue = deque(["a"])
while queue:
node = queue.popleft()
for n in graph[node]:
if n not in distance:
distance[n] = distance[node] + 1
queue.append(n)
print(distance)It prints
{'a': 0, 'b': 1, 'c': 2}
Try it yourself
What does BFS use to decide what to visit next?
- A stack
- A queue
- A dictionary
- Random choice
Answer it in the app
🕳️ Going Deep
One word different
Depth-first search follows one path as far as it goes before backing up. The code is BFS with the queue swapped for a stack — pop instead of popleft. That is genuinely the only change.
Python
graph = {
"a": ["b", "c"],
"b": ["d"],
"c": [],
"d": [],
}
def dfs(start):
seen = []
stack = [start]
while stack:
node = stack.pop()
if node in seen:
continue
seen.append(node)
print(node)
for neighbour in graph[node]:
stack.append(neighbour)
dfs("a")It prints
a c b d
Or let recursion hold the stack
Recursion already keeps track of where to go back to, so DFS is often written without a stack at all.
Python
graph = {
"a": ["b", "c"],
"b": ["d"],
"c": [],
"d": [],
}
seen = []
def dfs(node):
if node in seen:
return
seen.append(node)
print(node)
for neighbour in graph[node]:
dfs(neighbour)
dfs("a")It prints
a b d c
Try it yourself
What is the real difference between BFS and DFS?
- BFS is always faster
- Which container holds the waiting nodes — a queue for BFS, a stack for DFS
- DFS visits fewer nodes
- BFS cannot handle loops
You want the fewest steps between two places. Which do you use?
- DFS
- BFS
- Either
- Neither
Answer them in the app
🗺️ Finding a Way Through
Can I get there at all?
Once you can visit everything reachable, "is there a route?" is just asking whether the place you want turned up.
Python
graph = {"a": ["b"], "b": ["c"], "c": [], "z": []}
def can_reach(start, target):
seen = []
stack = [start]
while stack:
node = stack.pop()
if node == target:
return True
if node in seen:
continue
seen.append(node)
for n in graph[node]:
stack.append(n)
return False
print(can_reach("a", "c"))
print(can_reach("a", "z"))It prints
True False
Remembering the way back
To get the actual route, record which node you *came from*. Then walk that trail backwards from the finish.
Python
from collections import deque
graph = {"a": ["b"], "b": ["c"], "c": []}
came_from = {"a": None}
queue = deque(["a"])
while queue:
node = queue.popleft()
for n in graph[node]:
if n not in came_from:
came_from[n] = node
queue.append(n)
path = []
at = "c"
while at is not None:
path.append(at)
at = came_from[at]
print(path[::-1])It prints
['a', 'b', 'c']
Try it yourself
What does this print?
Python
path = ["c", "b", "a"]
print(path[::-1])Why does BFS give the shortest path?
- It tries every path and picks the best
- It reaches each node by the fewest steps first, so the first way it finds is the shortest
- It sorts the nodes
- It does not
Answer them in the app
🏆 Graph Master
Try it yourself
What does this print?
Python
g = {"a": ["b", "c"], "b": [], "c": []}
total = 0
for node in g:
total = total + len(g[node])
print(total)Answer it in the app