Breadth First Search/Depth First Search Animations

Breadth First Search/Depth First Search Animations
Breadth-first search (BFS) and depth-first search (DFS) are two distinct orders in which to visit the vertices and edges of a graph. BFS radiates out from a root to visit vertices in order of their distance from the root. Thus closer nodes get visited first. DFS prefers to visit undiscovered vertices immediately, so the search trees tend to be deeper rather than balanced as with BFS. Notice that the DFS consists of three ``Hamiltonian'' paths, one in each component -- while the BFS tree has far more degree-3 nodes, reflecting balance.

Download: bfs.gif - The BFS Animation. dfs.gif - The DFS Animation. bfsdfs.nb - Notebook file.
These animations were produced using Combinatorica -- see www.combinatorica.com and our book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica for more information. Check out our dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations!