Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Graphs Overview

BFS finds the shortest path (fewest edges)
step 1 / 31
undirected graph — BFS from A
A
B
C
D
E
F
queue (FIFO)
front →
(empty)
← back
BFS shortest paths
▸
1bfs(graph, source):
2    dist = {}
3    dist[source] = 0
4    queue = [source]
5    while queue not empty:
6        u = queue.dequeue()      // front
7        for v in adj[u]:
8            if v not in dist:
9                dist[v] = dist[u] + 1
10                queue.enqueue(v)  // back
11    // dist[v] = fewest edges from source
state
  • nodes (V)6
  • edges (E)7
  • sourceA

line 1Breadth-First Search explores a graph in RINGS around the source. Ring 0 is the source itself; ring 1 is everything one edge away; ring 2 is two edges away; and so on. The big payoff: BFS finds the SHORTEST PATH (fewest edges) from the source to every node. Here A reaches the far node F two ways — A→B→D→F and A→C→E→F — and BFS will show why the FIRST time we touch a node is always along a shortest route.