Breadth-first and depth-first search (BFS and DFS)

In short: Breadth-first and depth-first search are two ways to traverse a graph or tree completely. BFS goes level by level, DFS as deep as possible before backing up.

In more detail: BFS uses a queue (queue) and in an unweighted graph finds the shortest path (measured in edges). DFS uses a stack (stack) or recursion (recursion) and suits mazes, cycle detection and topological sorting. Both take O(V + E) time.

In Depth

• BFS: put the start in the queue, always take the front node, append its unvisited neighbours at the back.
• DFS: visit the next unvisited neighbour, go back at a dead end (backtracking).
• Visited marking: prevents infinite loops with cycles.
• Examples: shortest path in a maze (BFS), connected components (DFS), networks, social contacts (“degrees of separation”).
• Memory: BFS needs a lot of space for wide graphs, DFS for deep ones.

See also: Graph data structure, Dijkstra’s algorithm, Big O notation