Visited
In the queue
Edges checked

  • Current
  • In the queue
  • Visited
  • Path
A click on a node sets

More about breadth-first search

Breadth-first search (BFS)

Breadth-first search explores a graph in rings: first every node next to the start, then every node two edges away, and so on. It does that with a queue, first in, first out. Click a node to start from it, pick a goal if you like, and step through the search to see the queue grow and shrink, each node get its distance, and a shortest path appear. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Click a node to make it the start; switch the click to Goal and click another node to look for a shortest path to it. The number on each node is its distance from the start, and the row under the graph is the queue. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.

How it works

  1. Click a node to make it the start. To look for a path, switch the click to Goal and click another node.
  2. Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the search.
  3. Watch the queue under the graph and the distance on each node. New graph makes another graph to try.

How breadth-first search works

Put the start node in a queue with distance 0. Then repeat: take the node at the front of the queue and look at each of its neighbours. A neighbour that has not been seen yet gets a distance one higher than the node you took, remembers that node as the way it was reached, and joins the back of the queue. Neighbours seen before are skipped. When the queue is empty, every node that can be reached has its distance.

Why it finds shortest paths

The queue hands out nodes in the order they were found, and nodes are found ring by ring: all nodes at distance 1 are queued before any at distance 2, and so on. So the first time a node is reached, it is reached by a path with the fewest possible edges. Following the remembered nodes back from the goal to the start gives that path. This only counts edges; when edges have different lengths, Dijkstra's algorithm is needed.

Frequently asked questions

What is breadth-first search?

A way to explore a graph from a start node by visiting all its neighbours first, then their neighbours, and so on, ring by ring. It uses a queue to keep the nodes in the order they were found.

Does breadth-first search find the shortest path?

Yes, when every edge counts the same: the first time BFS reaches a node, it has used the fewest possible edges. For edges with different lengths, use Dijkstra's algorithm instead.

What is the difference between BFS and DFS?

Breadth-first search uses a queue and spreads out evenly, ring by ring. Depth-first search uses a stack (or recursion) and follows one path as deep as it goes before backing up. BFS finds shortest paths in edges; DFS does not, but it is handy for finding cycles and for topological sorting.

How fast is breadth-first search?

It takes each node off the queue once and looks along each edge from both ends, so the work grows with the number of nodes plus the number of edges.

Is my graph sent anywhere?

No. The graph is made and searched in your browser, and your last settings stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor