Graph Traversal Playground

Simple graph traversal visualiser. There are lots of websites that show you physically traversing nodes but this does not build intuition for why different traversal methods are better in specific situations.

This visualiser uses a grid (each node is a square on the grid). A node’s neighbours are the four white nodes to each side of it (up, right, down, left). You can block off paths by clicking on squares and then, those can not reachable (ie. no longer neighbours). You must set a source and a target however, you can create graphs where it is impossible to reach the target from the source. You will notice that no matter which algorithm you select, if it is impossible to reach the target, all reachable nodes will be traversed.

A special case of this is IDDFS, which will continue iteratively deepening even once it has visited all reachable nodes (infinitely). This is based on the algorithm I learnt for it at university but I am sure better versions of the algorithm check whether additional nodes are visited on each depth increase and terminate when no new nodes are visited.

Using the visualiserPermalink

UsagePermalink

1. Click and/or drag to draw walls (black)
2. Right click to set source (green)
3. Right click again to set target (red)

VisualisationPermalink

1. Yellow cells show explored nodes, light green shows nodes in the queue
2. Blue path shows the final optimal route found

You can find a summary of these algorithms below the visualiser

Graph Traversal Visualisation

Algorithm: A* Search (Manhattan Distance) Breadth-First Search Depth-First Search Iterative Deepening DFS Greedy Best-First (Manhattan Distance)

Grid Size: 8x6 (Huge) 20x15 (Large) 40x30 (Medium) 60x45 (Small) 80x60 (Tiny)

Speed:

Slow Fast

Start Point

End Point

Wall

Visited

In Queue

Final Path

0

Path Length

0

Nodes Visited

Algorithm OverviewPermalink

• A* Search - Heuristic Search (Manhattan distance heuristic) that gives shortest path
• BFS - Regular Breadth First Search Algorithm (will return shortest path) but uses a lot of space
• DFS - Regular Depth First Search Algorithm (will not return shortest path) but is memory efficient
• IDDFS - Combines DFS space efficiency but finds shortest path by iteratively increasing depth limits (DFS over 1 max depth then 2 max depth etc etc)
• Greedy Best-First - Fast heuristic search but may not find shortest path