Graph search: BFS and DFS
Maps, friend lists, web links and computer networks are all graphs: things joined to other things. Searching one means visiting every node you can reach, without going round in circles. Step through breadth-first search and depth-first search on the same 7-node graph, watch the queue and the stack that drive them, and see why only one of them finds shortest paths.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01Breadth-first search keeps the nodes it still has to visit in which structure?
BFS takes the node that has waited longest. That is a queue (first in, first out), which is why it finishes every node 1 edge away before any node 2 edges away.
02On the lesson's graph, starting at A, what order does BFS visit the nodes in?
A first, then its neighbours B and C, then their new neighbours D, E and F, then G. A B D G E F C is the depth-first order.
03What does the seen set stop?
E and F both lead to G, which is already seen, so G is not added again. Without the check, a graph with a loop would make the search go round forever.
04DFS reached C along A, B, D, G, F, C. What does that tell you?
DFS follows one path as deep as it can, so the path it finds can be long. BFS reaches C in 1 edge because it explores level by level.
05Edges now have costs, and you want the cheapest route. Which algorithm fits?
BFS counts edges, not costs. Dijkstra's algorithm always takes the cheapest node next from a priority queue; OSPF routers use it to pick routes by link cost.
Glossary
- Graph
- A set of nodes (also called vertices) joined by edges, such as places joined by roads.
- Neighbour
- A node one edge away. A graph is often stored as a list of neighbours for each node (an adjacency list).
- Queue
- A line where the first item in is the first out (FIFO). Python's collections.deque is a fast queue.
- Stack
- A pile where the last item in is the first out (LIFO). Recursive calls form a stack.
- Breadth-first search (BFS)
- Explores level by level with a queue; finds the fewest edges from the start in an unweighted graph.
- Depth-first search (DFS)
- Follows one path as far as it can, then backtracks; uses a stack or recursion.
- Seen set
- The record of nodes already found, so none is added twice and loops cannot trap the search.
- O(V + E)
- Work that grows with the number of nodes (V) plus the number of edges (E).
Notes and sources
- A Python list can act as a queue, but list.pop(0) has to shift every other item. collections.deque is built for fast appends and pops at both ends, so BFS uses it.
- A Python set has no order. The drawing lists the seen set in the order nodes were added, to make it easy to follow.
- Python limits how deep recursion can go (sys.getrecursionlimit() is 1000 by default). For very deep graphs, DFS uses an explicit list as a stack instead of recursion.
- O(V + E) assumes adjacency lists, as here. If the graph is stored as a V by V table (an adjacency matrix), finding neighbours costs O(V) per node, so both searches take O(V²).
- Dijkstra's algorithm needs edge costs that are zero or more. OSPF routers run it on the link costs of their area to build their routing tables (RFC 2328, section 16.1).
- Both searches try neighbours in alphabetical order. A different order gives a different but equally valid visit order; BFS distances stay the same.
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 4th ed. (MIT Press), ch. 20 and 22
- Sedgewick and Wayne: Algorithms, 4th ed., 4.1 Undirected graphs
- MIT 6.006 Introduction to Algorithms (Spring 2020): BFS, DFS and Dijkstra lectures
- Dijkstra (1959): A note on two problems in connexion with graphs
- RFC 2328: OSPF Version 2, section 16.1 (shortest-path tree)
- Python library: collections.deque
- Python tutorial: Using lists as stacks and queues
- Python library: heapq (priority queue)
Quiz Unlocks after the last step.