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 targetStack, last in, first outStacklast in, first out
  • Being taken

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

The graph has 77 nodes and 77 edges, and nothing has been explored yet. Depth-first search starts at row 1, column 1 and keeps a stack.
  1. 1put the start on the stack
  2. 2take the node from the top of the stack
  3. 3already visited, so throw this copy away
  4. 4visit it, and record how long the route to it was
  5. 5push each neighbour on top, so the last one pushed is looked at next
  6. 6stop: either the target came off the stack, or the stack emptied and there is no path
Nodes visited
0
Edges examined
0
Pushed on the stack
0
Deepest the stack 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.

Depth-first search

Depth-first search keeps a stack instead of a queue. It takes the most recently added node, looks at its neighbours, and pushes the unseen ones on top — so the next node it examines is one it has only just discovered. The effect is that it walks as far as it can along one route, and only when that route is exhausted does it back up to the most recent junction it has not finished with.

Its frontier

A stack, taken from the top.

When it is the right choice

It is the natural choice when you need to visit everything rather than to find something close: enumerating every path, detecting cycles, finding strongly connected components, topological ordering by finish time, or exploring a tree. Its memory is bounded by the length of the current path rather than by the width of the graph, which is the opposite trade-off from breadth-first search. What it does not give you is a shortest path — the distances it records are the lengths of the routes it happened to take.

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