Graphs: places and ways between them

A graph is made of nodes and the edges that join them: cities and roads, pages and links, the cells of a maze and the ways between them. Unlike a tree it has no root and no direction: a node can be reached by more than one way, and the ways can form loops.

1graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
2stack = ["a"]
3seen = {"a"}
4while stack:
5    node = stack.pop()
6    for nxt in graph[node]:
7        if nxt not in seen:
8            seen.add(nxt)
9            stack.append(nxt)

The usual way to hold a graph is an adjacency list: next to each node, its neighbours. To walk it you keep the nodes still to visit on a stack; when a node comes off, its unseen neighbours go on. This is depth-first search (DFS): it follows one way to its end and then comes back.

A grid is a graph too, only its adjacency list is not written down: a cell's neighbours are the cells above, below, left and right of it. The bot that follows a wall through a maze is walking a graph.

Tasks