Where it runs
1. The problem
In the last lesson you learned to store a graph as an adjacency list: each node has its own list of direct neighbours. Now the graph is in memory, and you can walk it.
Take a subway map. Stations are dots (nodes), tracks between them are lines (edges). You stand at one station and want to know: which stations can you reach, and how many stops away is each one?
The same questions come up about friends and friends of friends, web pages and the links between them, rooms and doors. Whenever you need to spread out from one node and reach the others, you need a graph walk (a traversal).
Walking a graph is harder than walking a list, because a graph can have cycles. Two routes can lead to the same station. If you follow the links without marking anything, you go round in circles forever.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedbfsDistances({0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1, 5], 4: [2, 5], 5: [3, 4, 6], 6: [5]}, 0)Find the fewest edges from node 0 to every other node. Node 0 is marked with dist 0 and put in the queue.
Recognise it
Say these words and it is this pattern
- shortest path in an unweighted graph
- fewest steps/hops between nodes
- can node X reach node Y
- explore ring by ring / layer by layer
- graph given as adjacency list, may contain cycles
Looks similar, isn't
- Tree traversal
A tree cannot reach a node twice, so it needs no visited set. A graph can, so it always does.
- Dijkstra's algorithm
Weighted edges break the level order. A heap then replaces the queue.
- Connected components
That page counts the groups in a graph. This is the walk that each count is built from.
- Backtracking
Backtracking undoes its state on the way out. A traversal marks a node and never unmarks it.
V nodes and E edges give O(V + E). Memory is O(V) for the visited set and the frontier.
On LeetCode
Graph problems about what you can reach from a start, or the fewest edges to get there. BFS with a queue and a visited set reaches nodes ring by ring, so the first time it reaches a node is along a shortest path.
Build the adjacency list, run BFS from source, and check whether destination was visited.
The keys in each room are its edges, so BFS from room 0 and check that every room was visited.
Walk the graph with BFS, and let the visited map hold the copy of each node so edges can point to it.
Words are nodes and one changed letter is an edge, so the lesson's distances give the shortest ladder.