Core · AlgorithmsLesson 7 of 8Free to read

Graphs: BFS and DFS · Data Structures and Algorithms

How do you explore a network of connected things?

Why you need it

Maps, social networks, web links, course prerequisites and folder trees are all graphs: things (nodes) joined by connections (edges). Two traversals, breadth-first search (BFS) and depth-first search (DFS), answer most graph questions: can I get there, how many steps, what's connected.

The intuition

Store a graph as a dict: each node → list of neighbours (an adjacency list).

BFS uses a queue: visit all neighbours at distance 1, then distance 2, … like ripples in water. The first time you reach a node is by the fewest steps.
DFS uses a stack (or recursion): go as deep as possible down one path, then back up. Good for "is everything reachable?" and for trees.

Both keep a visited set, so a node is never processed twice and cycles don't loop forever.

A tree is a graph with no cycles and one root: folders, a family tree, a parsed web page.

Definition

Graph

Nodes connected by edges. Edges may have a direction (A follows B) or a weight (a distance).

BFS and DFS

Breadth-first search explores level by level with a queue and finds shortest paths in unweighted graphs. Depth-first search follows one path deep with a stack or recursion.

Examples

Fewest steps with BFS

Try it yourself

How many streets from home to the library?

graph = {
    "home": ["park", "shop"],
    "park": ["home", "lake"],
    "shop": ["home", "school"],
    "lake": ["park", "school"],
    "school": ["shop", "lake", "library"],
    "library": ["school"],
}
from collections import deque

def steps(start, goal):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return -1

print(steps("home", "library"))

Step by step

L12dist doubles as the visited set.
L19Only unseen nodes join the queue, each once.
L24home → shop → school → library.3

Depth-first on a tree

Try it yourself

A folder tree. DFS with recursion prints each path, going deep first.

tree = {"/": ["docs", "src"], "docs": ["notes.md"], "src": ["app.py", "lib"], "lib": ["util.py"],
        "notes.md": [], "app.py": [], "util.py": []}

def walk(node, depth):
    print("  " * depth + node)
    for child in tree[node]:
        walk(child, depth + 1)

walk("/", 0)

Output

/
  docs
    notes.md
  src
    app.py
    lib
      util.py

Step by step

L5Indent by depth.
L7Finish everything under docs before moving on to src.

Common mistakes

Forgetting visited

On a graph with a cycle (home → park → home …) a traversal without a visited set runs forever.

DFS for shortest paths

DFS finds a path, not the shortest. In an unweighted graph, use BFS.

Quick quiz

1. What does this print?

graph = {
    "home": ["park", "shop"],
    "park": ["home", "lake"],
    "shop": ["home", "school"],
    "lake": ["park", "school"],
    "school": ["shop", "lake", "library"],
    "library": ["school"],
}
from collections import deque
order, seen = [], {"home"}
queue = deque(["home"])
while queue:
    node = queue.popleft()
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            seen.add(nxt)
            queue.append(nxt)
print(order[:4])

A
```
['home', 'park', 'shop', 'lake']
```
B
```
['home', 'park', 'lake', 'school']
```
C
```
['home', 'shop', 'park', 'lake']
```

Show the answer

Answer: A

BFS visits home's neighbours (park, shop) before anything two steps away.

2. You need the minimum number of moves in a maze where every move costs the same. Which traversal?

ABFS
BDFS
CEither always gives the minimum

Show the answer

Answer: A

BFS reaches each square first by the fewest moves.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictDepth-first order
Type exactly what this program prints.
ModifyStop the endless walk
reachable(graph, start) should return the set of nodes you can reach. It never ends on graphs with cycles. Add a visited check so each node is processed once.
WriteShortest path
Write path(graph, start, goal) that returns the list of nodes on a shortest path from start to goal (both included), or None if there is none. Use BFS and remember each node's parent, then walk back from the goal.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Graph	图	Nodes connected by edges.
Breadth-first search (BFS)	广度优先搜索	Explore level by level with a queue.
Depth-first search (DFS)	深度优先搜索	Explore one path deep before backing up.
Tree	树	A connected graph with no cycles and one root.