## 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
Check out our dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations! |