Tools Suite

Graph algorithms

O(V + E)·O(V) space
Whole graph

Drag to pan; pinch or Ctrl+scroll to zoom, which stops at the whole graph; arrow keys pan once the picture has focus.

r1c1 to r2c1r1c4 to r1c5r1c4 to r2c4r1c5 to r1c6r1c6 to r1c7r1c6 to r2c6r1c7 to r1c8r1c7 to r2c7r1c8 to r2c8r1c10 to r1c11r1c10 to r2c10r2c1 to r3c1r2c3 to r2c4r2c6 to r2c7r2c6 to r3c6r2c7 to r2c8r2c7 to r3c7r2c8 to r2c9r2c9 to r2c10r2c9 to r3c9r2c10 to r3c10r3c1 to r4c1r3c5 to r3c6r3c5 to r4c5r3c6 to r3c7r3c9 to r3c10r3c9 to r4c9r3c10 to r3c11r4c1 to r4c2r4c1 to r5c1r4c2 to r4c3r4c2 to r5c2r4c3 to r4c4r4c3 to r5c3r4c4 to r4c5r4c4 to r5c4r4c5 to r5c5r4c8 to r4c9r4c8 to r5c8r4c9 to r5c9r5c1 to r5c2r5c1 to r6c1r5c2 to r5c3r5c2 to r6c2r5c3 to r5c4r5c4 to r5c5r5c4 to r6c4r5c5 to r5c6r5c5 to r6c5r5c6 to r5c7r5c7 to r5c8r5c7 to r6c7r5c8 to r5c9r5c8 to r6c8r5c9 to r6c9r6c1 to r6c2r6c1 to r7c1r6c4 to r6c5r6c4 to r7c4r6c5 to r7c5r6c7 to r6c8r6c7 to r7c7r6c8 to r6c9r6c8 to r7c8r6c9 to r6c10r6c9 to r7c9r6c10 to r6c11r6c10 to r7c10r6c11 to r7c11r7c3 to r7c4r7c4 to r7c5r7c5 to r7c6r7c6 to r7c7r7c7 to r7c8r7c8 to r7c9r7c9 to r7c10r7c10 to r7c11Row 1, column 1, the startRow 1, column 2, a wallRow 1, column 3, a wallRow 1, column 4Row 1, column 5Row 1, column 6Row 1, column 7Row 1, column 8Row 1, column 9, a wallRow 1, column 10Row 1, column 11Row 2, column 1Row 2, column 2, a wallRow 2, column 3Row 2, column 4Row 2, column 5, a wallRow 2, column 6Row 2, column 7Row 2, column 8Row 2, column 9Row 2, column 10Row 2, column 11, a wallRow 3, column 1Row 3, column 2, a wallRow 3, column 3, a wallRow 3, column 4, a wallRow 3, column 5Row 3, column 6Row 3, column 7Row 3, column 8, a wallRow 3, column 9Row 3, column 10Row 3, column 11Row 4, column 1Row 4, column 2Row 4, column 3Row 4, column 4Row 4, column 5Row 4, column 6, a wallRow 4, column 7, a wallRow 4, column 8Row 4, column 9Row 4, column 10, a wallRow 4, column 11, a wallRow 5, column 1Row 5, column 2Row 5, column 3Row 5, column 4Row 5, column 5Row 5, column 6Row 5, column 7Row 5, column 8Row 5, column 9Row 5, column 10, a wallRow 5, column 11, a wallRow 6, column 1Row 6, column 2Row 6, column 3, a wallRow 6, column 4Row 6, column 5Row 6, column 6, a wallRow 6, column 7Row 6, column 8Row 6, column 9Row 6, column 10Row 6, column 11Row 7, column 1Row 7, column 2, a wallRow 7, column 3Row 7, column 4Row 7, column 5Row 7, column 6Row 7, column 7Row 7, column 8Row 7, column 9Row 7, column 10Row 7, column 11, the targetQueue, first in, first outQueuefirst in, first out
  • Being taken

The graph has 77 nodes and 77 edges, and nothing has been explored yet. Breadth-first search starts at row 1, column 1 and keeps a queue.

The graph has 77 nodes and 77 edges, and nothing has been explored yet. Breadth-first search starts at row 1, column 1 and keeps a queue.
  1. 1put the start in the queue, at distance zero
  2. 2take the node at the front of the queue
  3. 3a neighbour never reached before: record its distance and add it to the back
  4. 4a neighbour already reached, so leave it alone
  5. 5stop: either the target came out of the queue, or the queue emptied and there is no path
Nodes settled
0
Edges examined
0
Added to the queue
0
Largest the queue got
0

Complexity

BestO(V + E)
AverageO(V + E)
WorstO(V + E)
Extra spaceO(V)
V + E at n=77 predicts 154; this run took 0.

Breadth-first search

Breadth-first search keeps a queue of nodes it has reached but not yet looked at. It takes the oldest one, looks at each of that node’s neighbours, and adds any it has never seen to the back of the queue. Because the queue is first in, first out, every node at distance one is dealt with before any node at distance two, which is why the first arrival at a node is always by a fewest-edges path.

Its frontier

A queue, taken from the front.

When it is the right choice

It is the right choice whenever "fewest steps" is the question and every step costs the same: a maze, a friend-of-a-friend search, the number of moves to solve a puzzle. It is also the cheapest way to find out whether two nodes are connected at all. What it cannot do is take weights into account — on a weighted graph it finds the path with the fewest edges, which is often not the cheapest one, and that is Dijkstra’s job rather than a flaw in this.

How it works

Worth noticing

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Extra space
O(V)
Runs on
a grid with walls; a weighted undirected graph; a directed acyclic graph; a directed graph with a cycle
Largest grid
11 by 7 cells
Largest graph
14 nodes, 28 edges

The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.

Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.

Worth comparing

All graph algorithms