A graph is nodes plus edges. Cities and roads are a graph. An adjacency list is a map from a city to its neighbours. Breadth-first search (BFS) uses a queue and finds a shortest hop-path.

Goal

BFS from Nairobi and print the hop distance to Eldoret.

Adjacency list

graph = {
    "Nairobi": ["Nakuru", "Mombasa"],
    "Mombasa": ["Nairobi", "Kisumu"],
    "Kisumu": ["Mombasa", "Nakuru"],
    "Nakuru": ["Nairobi", "Kisumu", "Eldoret"],
    "Eldoret": ["Nakuru"],
}
print(sorted(graph))
print(graph["Nakuru"])

Undirected: if A lists B, B should list A.

BFS hops

from collections import deque

def hops(graph, start, goal):
    if start == goal:
        return 0
    seen = {start}
    q = deque([(start, 0)])
    while q:
        node, dist = q.popleft()
        for nbr in graph[node]:
            if nbr in seen:
                continue
            if nbr == goal:
                return dist + 1
            seen.add(nbr)
            q.append((nbr, dist + 1))
    return -1

graph = {
    "Nairobi": ["Nakuru", "Mombasa"],
    "Mombasa": ["Nairobi", "Kisumu"],
    "Kisumu": ["Mombasa", "Nakuru"],
    "Nakuru": ["Nairobi", "Kisumu", "Eldoret"],
    "Eldoret": ["Nakuru"],
}
print("Nairobi to Eldoret", hops(graph, "Nairobi", "Eldoret"))
print("Nairobi to Nairobi", hops(graph, "Nairobi", "Nairobi"))

From a file

Download graph.json, Add files, then:

import json
from collections import deque
from pathlib import Path

def hops(graph, start, goal):
    seen = {start}
    q = deque([(start, 0)])
    while q:
        node, dist = q.popleft()
        if node == goal:
            return dist
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr)
                q.append((nbr, dist + 1))
    return -1

graph = json.loads(Path("graph.json").read_text(encoding="utf-8"))
print(hops(graph, "Mombasa", "Eldoret"))

Pitfall

BFS without a seen set loops forever on a cycle. Mark a node when you first enqueue it.