Course 3.1Lesson 4 of 5
A graph is a set of points, called nodes, and the lines between them, called edges, and it can describe a map of towns and roads, a network of friends, or the links of a website. In Python a graph is a dictionary that maps each node to the list of its neighbours. Breadth-first search uses a queue, visits the places in rings, nearest first, and so finds the path with the fewest steps. A dictionary of the place from which each place was reached marks what has been seen and lets the path be rebuilt backwards. Depth-first search goes as far as it can and then comes back, and finds everything that can be reached from a start and the separate groups of a graph. A node that is not seen again must be recorded, or a loop in the graph would make the search go round for ever.
Try the code and the simulations beside the lesson.
After this lesson you can
A graph is a set of nodes (points) and edges (the lines between them). It is the right picture for anything with connections: towns and roads, people and friendships, web pages and links, computers in a network. A tree is a special graph with no loops. A graph may have loops.
In Python, the simplest way to store a graph is a dictionary of neighbours: each key is a node, and its value is the list of the nodes that it is joined to.
A graph where lines have a direction (a one-way street) lists a neighbour only on one side.
How many steps from Asha to Ana? You could try every route, but there is a neat method: breadth-first search (BFS). Start at the first place, visit all its neighbours, then their neighbours, and so on, in rings, like the ripples of a stone in a pond. The first time you reach the goal, you came by the fewest steps.
The tool is a queue: the places to visit, in order of discovery. New places join at the back, and the one that has waited longest is visited first. This is why the queue of the first lesson matters.
Predict first. What is the shortest path from Asha to Ana? Then run it.
The results: Asha to Ana is ['Asha', 'Ravi', 'Meera', 'Ana']: 3 steps. Kabir to Meera is ['Kabir', 'Ravi', 'Meera']. Asha to Asha is ['Asha']: no steps. Asha to Zoya, who has no friends, is None.
Why if neighbour not in previous? Look at the friends: Asha knows Ravi, and Ravi knows Asha. Without the check, the search would go Asha, Ravi, Asha, Ravi, ... for ever. A graph may have loops, so a search must remember where it has been.
Another way to search is to go as deep as you can along one path, and come back when you are stuck, like walking through a maze with one hand on the wall. This is depth-first search (DFS). It is natural with recursion, which uses the call stack as its memory.
groups uses it to find the separate groups: take a person not yet done, find everyone reachable, and mark them done. The graph has two groups: the five friends, and Dev with Zoya.
Because the queue serves the oldest first, everyone one step away is visited before anyone two steps away. That is why BFS finds the shortest way.
| BFS (a queue) | DFS (recursion, or a stack) | |
|---|---|---|
| Visits | in rings, nearest first | along one path as deep as it goes |
| Finds | the shortest path in steps | everything that is reachable |
| Good for | fewest steps, nearest first | groups, can I get there, mazes, sorting tasks |
Both visit each place once, so both take time in proportion to the number of nodes and edges.
graph[place] is a KeyError. Every node needs an entry, even if its list is empty.None.Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.
Then the labs and the problems:
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
shortest_path give when the goal cannot be reached?Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…
This lesson is free to read. Enroll free to keep your place and take the tests.