Graphs, BFS & DFS
Nodes connected in any pattern at all, social networks, maps, dependencies, and the two traversals that explore them.
- Represent a graph as an adjacency list
- Trace breadth-first and depth-first traversal over the same graph
- Explain why BFS finds the shortest path in an unweighted graph
Finish first
Cost at a glance
- bfs
- O(V + E)
- dfs
- O(V + E)
- space
- O(V)
Topic contents
Lesson 1 of 2
Connections without hierarchy
A tree is a graph with rules. Drop the rules, allow any node to connect to any other, allow cycles, allow a node to have many parents, and you have a graph. Friend networks, road maps, package dependencies and web links are all graphs.
Because cycles are allowed, traversal needs something trees never needed: a record of what has already been visited. Skip that and BFS will happily loop forever between two mutually connected nodes.
Graph traversal: BFS and DFS
Watch the frontier grow level by level under BFS, then dive and backtrack under DFS.
Graph traversal, BFS
O(V + E) time · O(V) spaceStart
Breadth-first search starts at A, which goes into the queue and is marked visited straight away. Marking on discovery, not on visit, is what stops a cycle from re-adding it.
Lesson 2 of 2
Same graph, two orders
Run BFS and then DFS from the same starting node in the visualizer and compare the order of visits. BFS finishes all of a node's immediate neighbours before going deeper, which is why it finds the shortest path in an unweighted graph: the first time it reaches a node, it arrived by the fewest possible hops.
DFS commits to one path until it dead-ends, then backtracks. That makes it the natural fit for questions about reachability, cycle detection and topological ordering.
Worked examples
Read the code, then change it
Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const neighbour of graph[node]) {
if (!visited.has(neighbour)) {
visited.add(neighbour); // guard against cycles
queue.push(neighbour);
}
}
}
return order;
}
const graph = { A: ['B', 'C'], B: ['A', 'D'], C: ['A', 'D'], D: ['B', 'C'] };
console.log(bfs(graph, 'A'));Practice
Work these out yourself
No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.
0/3 attemptedAssessment
Check your understanding
Answer each question, then read the explanation. That is where the learning is.
Finished this topic?
0 of 2 lessons marked done. Marking the topic complete ticks the rest.