GraphLab

Graph theory & algorithm visualizer
About BFS and DFS

GraphLab › BFS and DFS

BFS and DFS Visualizer: Breadth-First and Depth-First Search

Breadth-first search (BFS) and depth-first search (DFS) are the two basic ways to visit every vertex of a graph that can be reached from a start vertex.

Breadth-first search

BFS uses a queue. It visits the start vertex, then all its neighbours, then their neighbours, and so on, level by level. In an unweighted graph this gives the path with the fewest edges.

Depth-first search

DFS uses a stack. It goes as deep as possible along one path, then backtracks to the last vertex that still has an unvisited neighbour. It is used for finding cycles, topological sorting and connected components.

Try it in GraphLab

The search starts from the first vertex. Tap any vertex to start from it instead. Each step shows the current vertex, the queue or stack, and the visit order. Choose Depth-first search in the Algorithm menu to compare the two.

More topics