Breadth-first and depth-first traversals explore graphs.
BFS explores neighbours level by level using a queue and finds shortest paths in unweighted graphs; DFS dives deep using a stack or recursion and supports topological sort, cycle detection and connected components. Both run in O(V+E).
A maze solver uses BFS to find the shortest path.
Breadth-first and depth-first searches explore graphs systematically, and they are the basis of many graph algorithms.
Breadth-first and depth-first traversals explore graphs.
Breadth-first and depth-first searches explore graphs systematically, and they are the basis of many graph algorithms.
Use BFS to find shortest paths measured in hops, and DFS for tasks such as topological ordering or exploring all paths.
The queue keeps nodes in order of distance from the start, so each level is explored before the next.
Typical applications include finding the fewest hops between two users in a social network with BFS, checking whether a dependency graph contains a cycle with DFS and testing whether a maze has a path from start to exit.
Study "Graphs" first (topic 25 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Visited set avoids loops. Level order. Backtracking relation.
A maze solver uses BFS to find the shortest path.
The next topic is "Shortest path algorithms", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 26 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.