Breadth-First Search (BFS) Calculator

Read the Theory Guide →

Build an unweighted graph, choose a start and goal, and run BFS to see the FIFO queue and visited nodes at every step. Edit the graph or its direction and rerun to compare the paths BFS finds.

What You Can Explore

  • Build a graph on the canvas, or edit the preloaded one by adding, moving, and connecting nodes.
  • Switch between directed and undirected graphs to change which connections BFS can follow.
  • Choose the Starting Point and Goal Point, then press Run BFS to search the graph.
  • Step through the resolution to follow the FIFO queue, the node being evaluated, and the Closed List at each step.
Core Mechanics
▼
  • The FIFO Queue: BFS strictly runs on "First-In, First-Out". You must pop the oldest node from the *front* to evaluate it, and push its new neighbors to the *back*.
  • Level-by-Level Expansion: It completely finishes exploring depth dd before ever touching depth d+1d+1. This guarantees the shortest path based on *hop count*, ignoring edge costs.
  • Never Look Back: Once a node enters the Closed List (Visited), ignore it forever. Because BFS expands outward like a ripple, the *first* time you discover a node is mathematically guaranteed to be the fastest route to it.
  • The Goal Test (The Final Pop): Even if you see the goal waiting in the Open List, do not stop! You can only declare victory when the goal node is officially *popped* from the front and becomes the Evaluating Node.
Initializing Workspace...

Understanding Your Result

The path and step-by-step trace come from your graph and the selected start and goal. The summary shows the path BFS found and how many edges it crosses, while the queue trace shows the order in which nodes were explored.

  • Total Path Steps counts the edges in the returned path. Because BFS works on an unweighted graph, it does not use edge costs.
  • The Evaluating Node is the node at the front of the FIFO queue. Nodes discovered later wait behind nodes that were already queued.
  • The Closed List records nodes that have already been evaluated. A node can be explored without becoming part of the final path.
  • BFS explores the graph level by level, so in an unweighted graph the first path it finds to the goal uses the fewest edges.

Try These Experiments

Switch to Undirected

Setup: Run the preloaded directed graph with S as the start and G as the goal. Note the path and Total Path Steps.

Action: Switch the graph to undirected, keep the same start and goal, and run BFS again.

What to Observe: Compare the two paths. The directed run takes 4 edges through A, B, and C, while the undirected run can use M and reach G in 2 edges.

Takeaway: Edge direction determines which moves BFS can make. The connection between M and G points the wrong way in the directed graph, but becomes usable in both directions when the graph is undirected.

Add a Shortcut Edge

Setup: Run the directed preloaded graph with S as the start and G as the goal, where the current path crosses four edges.

Action: Connect A directly to C, then run BFS again without changing the start or goal.

What to Observe: Check the new path and Total Path Steps. Then inspect the Closed List to see whether B was still evaluated even though it is no longer part of the final path.

Takeaway: BFS can find a shorter path after a new connection is added, but nodes that were already queued can still be evaluated. The final path does not show all of the work BFS performed.

Pick an Unreachable Goal

Setup: Add a new node to the canvas and leave it unconnected. Keep S as the start and select the new node as the Goal Point.

Action: Run BFS and read the result. Then connect G to the new node and run BFS again.

What to Observe: The first run exhausts the reachable part of the graph without finding the goal. After adding the edge from G to the new node, BFS finds a route to it.

Takeaway: BFS can only find a goal that is reachable from the start by following the graph's allowed edge directions. A node can exist in the graph without being reachable from the chosen start.