Depth-First Search

Recursive DFS on an undirected graph from a start vertex. Reads the Algs4 Graph format (V, then E, then the edges). Watch the stack grow as Theseus's thread, and the adjacency-list iterators advance.

650ms
Graph G
unmarked
on stack
current vertex
finished
Ariadne thread
back edge (cycle)
passage examined (both mouths ⇒ explored)
explorer
Status
Press  Step  or  Play  to begin.
Stack  ·  Ariadne thread
empty
Bottom = start  ·  top = vertex being explored. Pop = backtrack along the thread.
Adjacency lists  ·  iterators
Edit / paste a graph
Format (Sedgewick & Wayne Graph): first line is the number of vertices V, second line is the number of edges E, then E lines each holding an undirected edge v w. Vertices are 0 … V−1. Parallel edges and self-loops are allowed. Adjacency lists are built by prepending (a Sedgewick Bag), so a vertex's neighbours appear in reverse order of how the edges were read — matching the booksite traversal order.