Welcome to Graph Traversal!

In this chapter, we are going to learn how computers "walk" through a graph to find information. Whether it’s Google Maps finding the quickest route to your favorite pizza place or Facebook suggesting a new friend, graph traversal algorithms are the secret sauce making it happen.

Don’t worry if graphs seem a bit messy at first—by the end of these notes, you'll see they are just logical puzzles waiting to be solved!

Prerequisite Refresh: What is a Graph?

Before we "traverse" (which is just a fancy word for "visit"), let’s remember what a graph is made of:

  • Vertices (or Nodes): These are the points or "circles" in our diagram (like cities on a map).
  • Edges (or Arcs): These are the lines connecting the nodes (like the roads between cities).

1. Breadth-First Search (BFS)

Think of Breadth-First Search as a "ripple in a pond." You start at one point and explore all the closest neighbors first, then move out to the next layer, and so on.

The "Level-by-Level" Strategy

BFS explores the graph layer by layer. You visit all nodes at distance 1, then all nodes at distance 2, etc. To keep track of which nodes to visit next, BFS uses a Queue data structure (First-In, First-Out).

Step-by-Step Process:

1. Pick a starting node and mark it as visited.
2. Add all its immediate neighbors into a Queue.
3. Take the first node out of the Queue.
4. If that node hasn't been visited, mark it as visited and add all its neighbors to the back of the Queue.
5. Repeat until the Queue is empty.

Real-World Analogy: The Social Media Search

Imagine you are looking for someone on LinkedIn. First, you look at your Direct Connections (Distance 1). If they aren't there, you look at Connections of Connections (Distance 2). You are searching broadly before going deeper.

Typical Application: Shortest Path

Because BFS explores everything close by first, it is the perfect tool for finding the shortest path in an unweighted graph (a graph where every road is the same length). It guarantees that when you find your target, you’ve taken the fewest number of edges to get there.

Quick Review: BFS
  • Data Structure: Uses a Queue.
  • Search Style: Wide/Broad.
  • Best for: Finding the shortest path.

2. Depth-First Search (DFS)

While BFS is like a ripple, Depth-First Search is like an explorer in a dark cave. You pick a path and follow it as deep as it goes until you hit a dead end, then you backtrack to the last junction and try a different path.

The "Go Deep" Strategy

DFS explores one branch of a graph completely before moving to the next. To manage this, DFS uses a Stack data structure (Last-In, First-Out) or Recursion.

Step-by-Step Process:

1. Pick a starting node and mark it as visited.
2. Move to an adjacent unvisited neighbor.
3. Repeat step 2 until you reach a node with no unvisited neighbors (a dead end).
4. Backtrack to the previous node and check for other unvisited neighbors.
5. The process ends when you have backtracked all the way to the start and all nodes are visited.

Real-World Analogy: Navigating a Maze

The official AQA syllabus mentions navigating a maze as the classic application for DFS. You keep walking down a corridor until you hit a wall, then you turn back and try the last side-turning you passed. You don't try every single hallway at once; you follow one to the end first.

Typical Application: Maze Solving & Game Logic

DFS is excellent for navigating mazes or puzzles where you need to see if a solution exists at the end of a long path. It uses less memory than BFS because it only needs to keep track of the current path it is on.

Quick Review: DFS
  • Data Structure: Uses a Stack (or Recursion).
  • Search Style: Deep.
  • Best for: Navigating a maze.

Comparing BFS and DFS

It’s very common for exams to ask you to choose between these two. Here is a simple way to remember the difference:

Memory Aid: The Alphabet Trick
- BFS = Breadth (Searching Wide)
- DFS = Depth (Searching Deep)

Common Pitfalls to Avoid:

  • Forgetting to mark nodes: If you don't mark a node as "visited," the computer might go in circles forever (an infinite loop!).
  • Queue vs. Stack: Students often swap these. Remember: BFS = Queue (Wait in line to expand wide) and DFS = Stack (Pile up the path to go deep).

Summary Takeaway

Graph traversal is the foundation of many complex algorithms. Remember these two key points for your AQA exam:

1. Breadth-First Search (BFS) uses a Queue to find the shortest path in unweighted graphs by looking at every neighbor first.

2. Depth-First Search (DFS) uses a Stack to explore a path to its limit and is famously used for navigating mazes.

Don't worry if tracing these feels slow at first. Grab a pen and paper, draw a few nodes, and try "walking" through them using a Queue or a Stack. It'll click in no time!