Exam practice

• Graph: things and the connections between them, drawn as dots and lines. Example: towns and the roads between them.
• Node: one of the things in a graph. Example: Bhaktapur in a graph of towns; a person in a graph of friends.
• Edge: a connection between two nodes. Example: the road from Bhaktapur to Banepa; a friendship.
• Directed graph: a graph whose edges go one way, drawn as arrows. Example: who follows whom on a social media app; links between web pages.
• Weighted graph: a graph with a number on each edge. Example: roads with their lengths in km, or their travel times.
• Tree: a joined-up graph with no loops, so there is exactly one route between any two nodes. Example: the folders on a phone; a family’s descendants from one ancestor.

Five nodes: Gate, Office, Library, Lab, Canteen. Edges: Gate–Office, Gate–Library, Office–Lab, Library–Lab, Library–Canteen (5 edges). It is undirected: every edge appears in both lists (Office is in Gate’s list and Gate in Office’s, and so on).
Degrees: Gate 2, Office 2, Library 3, Lab 2, Canteen 1. (They add up to 10, twice the 5 edges.) Gate, Office, Lab and Library make a loop, so it isn’t a tree.

Office is 3 steps from Canteen. Office came from Gate, Gate from Library, Library from Canteen: the route is Canteen → Library → Gate → Office. (Canteen → Library → Lab → Office is also 3 steps; the search found the one through Gate first, because Gate comes before Lab in Library’s list.)

Because of the queue, the search visits places in order of their steps: all places 1 step away are seen and visited before any place 2 steps away, all places 2 steps away before any at 3, and so on, in rings. So the first time a place is seen, it is in the earliest ring it can be in: if a route with fewer steps existed, the place would have been seen in that earlier ring. Its steps, written when it is first seen and never changed, are therefore the fewest.

When is a place marked as seen: when it is added to the list, or when it is visited?

The program marks a place as seen (steps[place] = …) only when it is visited, not when it is added. A place with several neighbors already on the list is added once by each of them, so the list fills with copies. Worse, d[nxt] can be overwritten by a later neighbor one ring further out before nxt is visited, so some places get too many steps. Mark a place as seen the moment it is added:

def breadth_first(graph, start):    steps = {start: 0}    to_visit = [start]    while len(to_visit) > 0:        place = to_visit.pop(0)        for nxt in graph[place]:            if nxt not in steps:                steps[nxt] = steps[place] + 1                to_visit.append(nxt)    return steps

The fewest steps counts the edges (roads) on a route; the shortest route adds up the edges’ weights (lengths or times). Breadth-first search treats every edge as one step, so it finds the fewest steps. In Figure 2.3, the fewest roads from Home to the Hospital is 2, through the Chowk, but that is 6.5 km; the shortest route takes 4 roads (School, Temple, Market) and is only 3.8 km. To find the shortest route, a search must visit places nearest first by distance, as Dijkstra’s algorithm does; this is how a map app works, with the weights being travel times.

A tree is a graph that is joined up and has no loops, so there is exactly one route between any two nodes; with n nodes it has n − 1 edges. Examples: the folders and files on a computer or phone (the main folder is the root, files are leaves); the internet’s names (.np → edu.np → a school’s name); the “came from” arrows left by a breadth-first search.
A search remembers what it has seen so that it doesn’t reach a node a second time by another route, or go round a loop forever. In a tree there is only one route to each node and no loops, so each node can be reached only once, and there is nothing to check.

Bhaktapur, Nagarkot, Banepa and Dhulikhel are cut off: in this simplified map, Thimi–Bhaktapur is the only road joining them to the rest (a bridge in the graph).
A new road from Kathmandu or Lalitpur to Bhaktapur (real maps have other roads, left out of this simplified one) would put the Thimi–Bhaktapur road in a loop: Kathmandu–Thimi–Bhaktapur–(new road)–Kathmandu. Then if any one road in the loop is closed, the towns can still be reached the other way round the loop. Sankhu, Budhanilkantha, Godawari and Pharping still hang on single roads, though, so for every town to stay reachable after any one closure, each of them needs a second road too. A graph is safe against any one closure only if every edge is part of a loop.

Nodes are students; edges join students who sit next to each other (both ways). Store it as a dictionary of neighbors. The flu spreads one edge per day, so “caught after 2 days” means “2 steps or fewer from the first student”: a breadth-first search.

1. Set days = {first: 0} and to_visit = [first].
2. While to_visit is not empty: take the student at the front; if their days are already 2, don’t spread further from them; otherwise, for each neighbor not in days, set their days to this student’s days + 1 and add them to the back.
3. The students in days (every one with 0, 1 or 2) have caught it after 2 days.

def caught_after(graph, first, days_limit):    days = {first: 0}    to_visit = [first]    while len(to_visit) > 0:        student = to_visit.pop(0)        if days[student] < days_limit:            for nxt in graph[student]:                if nxt not in days:                    days[nxt] = days[student] + 1                    to_visit.append(nxt)    return list(days)

Test it with days_limit 0 (only the first student), on a student who sits alone (only them), and on a small class drawn by hand.