Explores all nodes at current depth before going deeper. Uses a queue.
• Process: visit node, enqueue unvisited neighbours, dequeue next
• Complexity: O(V+E)
• Finds shortest path in unweighted graphs
• Uses: web crawling, social network connections, peer-to-peer networks
Goes as deep as possible before backtracking. Uses a stack (or recursion).
• Process: visit node, push unvisited neighbours, pop next
• Complexity: O(V+E)
• Does NOT guarantee shortest path
• Uses: maze solving, cycle detection, topological sort
Finds shortest paths from source to all nodes in a weighted graph. Greedy approach.
• Uses a priority queue (min-heap)
• Complexity: O((V+E) log V)
• Cannot handle negative edge weights
• Uses: GPS navigation, network routing (OSPF)
BFS
BFS(graph, start):
visited = {}
queue = [start]
visited.add(start)
WHILE queue not empty:
node = queue.dequeue()
process(node)
FOR each neighbour of node:
IF neighbour not in visited:
visited.add(neighbour)
queue.enqueue(neighbour)
DFS (iterative)
DFS(graph, start):
visited = {}
stack = [start]
WHILE stack not empty:
node = stack.pop()
IF node not in visited:
visited.add(node)
process(node)
FOR each neighbour of node:
IF neighbour not in visited:
stack.push(neighbour)
Graph: A–B:4, A–C:2, B–C:1, B–D:5, C–D:8, C–E:10, D–F:2, E–F:3. Find shortest path A→F.
| Step | Visit | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| Init | — | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | A (0) | ✓ | 4 | 2 | ∞ | ∞ | ∞ |
| 2 | C (2) | ✓ | 3 | ✓ | 10 | 12 | ∞ |
| 3 | B (3) | ✓ | ✓ | ✓ | 8 | 12 | ∞ |
| 4 | D (8) | ✓ | ✓ | ✓ | ✓ | 12 | 10 |
| 5 | F (10) | ✓ | ✓ | ✓ | ✓ | 12 | 10 ✓ |
Shortest path A→F = 10
Route: A → C (2) → B (3) → D (8) → F (10)
Unweighted graph. Click a start node, choose algorithm, then Step through.
Visited order:
1. Apply Dijkstra's algorithm to find the shortest path from A to F. Graph: A–B:4, A–C:2, B–C:1, B–D:5, C–D:8, C–E:10, D–F:2, E–F:3. Show your distance table at each step. [6 marks]
Mark scheme — 1 mark per correct step:
2. Describe one situation where BFS would be preferred over DFS, and explain why BFS is suitable for that situation. [3 marks]
Mark scheme:
3. Explain why Dijkstra's algorithm cannot be used on a graph with negative edge weights. [3 marks]
Mark scheme:
4. Describe the data structure used by BFS and explain why it produces a level-by-level traversal. [3 marks]
Mark scheme: