iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
BFS finds a path with the fewest edges in an unweighted graph; DFS explores deeply and backtracks, but does not generally find a shortest path; and uniform-cost search (UCS) finds a minimum-cost path when step costs are nonnegative. The right choice depends on what “shortest” means and how the graph’s edges are weighted.
What is the difference between BFS, DFS and UCS?
All three algorithms explore a graph by keeping track of discovered but not yet processed nodes in a frontier. Their key difference is which frontier item they process next.
| Algorithm | Next item chosen | Frontier structure | What it optimizes or does |
|---|---|---|---|
| Breadth-first search (BFS) | Shallowest node first | FIFO queue | Finds a minimum-edge path in an unweighted graph |
| Depth-first search (DFS) | Most recently discovered node | LIFO stack or recursion call stack | Explores one branch deeply, then backtracks |
| Uniform-cost search (UCS) | Path with the lowest accumulated cost | Min-priority queue | Finds a minimum-total-cost path when step costs are nonnegative |
How does BFS work, and when should you use it?
BFS explores outward from a starting node in layers: first the start, then nodes one edge away, then nodes two edges away, and so on. A FIFO queue preserves that order: the node discovered earliest is processed first. In an unweighted graph, this means the first time BFS reaches a destination, it has used the fewest edges possible. Boost.Graph and the University of Illinois CS 225 resource describe BFS this way: Boost.Graph traversal documentation and UIUC CS 225 BFS & DFS.
Quick wins for a faster PC:
Fix the driver behind crashes, sound loss and screen glitchesFind Drivers →Repair Windows errors before they cause bigger problemsFix Now →Use BFS for minimum-hop paths
Choose BFS when each move counts equally and you want the route with the fewest transitions—for example, the fewest links between two pages or the fewest moves in a maze where every move has the same cost. If the graph is disconnected, BFS reaches only the nodes reachable from its start unless you restart it from other unvisited nodes to traverse the whole graph.
#1 Best Overall
What BFS does not guarantee
BFS does not generally minimize total cost when edges have different weights. A route with fewer edges may be more expensive than a longer route. In that situation, use UCS rather than treating “shortest” as synonymous with “cheapest.”
How does DFS work, and when should you use it?
DFS follows one available branch as far as it can, then backtracks to try another. An iterative implementation uses a LIFO stack, which processes the most recently added item first; a recursive implementation uses the program’s call stack. DFS is useful for graph traversal and structural tasks such as cycle detection and topological sorting. See the Boost.Graph traversal documentation and Oregon State’s graph traversal material.
DFS is not a shortest-path algorithm
The first route DFS discovers to a destination depends on the order in which neighboring nodes are considered. It may find a longer route before a shorter one, so it does not generally guarantee either the fewest edges or the lowest total cost.
Do these 3 things before closing this tab:
1Clear out junk files and repair common Windows errors2Fix the driver behind crashes, sound loss and screen glitches3Repair Windows errors before they cause bigger problemsHow does uniform-cost search work?
UCS assigns each frontier path a cumulative cost, commonly written as g(n), and expands the path with the lowest total cost so far. A min-priority queue keeps the cheapest candidate at the front. Unlike BFS, UCS is not ordered by the number of edges; unlike heuristic best-first search, it does not use an estimate of how close a node is to the goal. Its priority is the cost already accumulated along the path. The UC Berkeley CS 188 chapter on uninformed search explains this search approach.
When UCS gives the cheapest path
With nonnegative step costs and the standard goal test—checking whether a node is the goal when it is selected for expansion—the first goal selected has minimum path cost. This makes UCS suitable when actions have different nonnegative costs, such as routes where roads carry different travel costs. UCS is closely related to Dijkstra’s algorithm: UCS can stop when it selects a goal, while Dijkstra’s algorithm is commonly used to compute distances beyond a single goal.
How do you choose the right algorithm?
| Your goal or situation | Choose | Reason |
|---|---|---|
| Fewest edges, with equal cost per step | BFS | It processes nodes in increasing depth, so the first reached goal uses the fewest edges. |
| Explore branches or perform structural graph analysis | DFS | Its stack-based order follows a branch and backtracks; it is useful for tasks such as cycle detection and topological sorting. |
| Lowest total cost, with different nonnegative step costs | UCS | It expands the path with the lowest accumulated cost, not the path with the fewest edges. |
Before choosing, answer two questions: are edges weighted, and do you care about the fewest transitions or the lowest accumulated cost? If every step has equal cost, minimizing edges also minimizes total cost, so BFS is appropriate. If costs differ, UCS is the relevant choice for a minimum-cost route under its nonnegative-cost assumption. If you only need to explore or analyze graph structure rather than find an optimal route, DFS may fit.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.What should you know about performance and memory?
For ordinary graph traversal using adjacency lists and visited tracking, BFS and DFS each run in O(V + E), where V is the number of vertices and E the number of edges. This bound is for that graph representation and traversal framing; search-tree analyses and other implementations may have different bounds. The current Boost.Graph traversal documentation describes the graph-traversal bound.
PC Slower Than It Used to Be?
A free scan shows the junk files, broken settings and background clutter dragging Windows down - then fixes them in one click.Free scan · Windows 10 & 11Outdated Drivers Are Slowing You Down
One free scan finds every outdated or missing driver and matches the right update for your exact hardware.Free scan · exact hardware matchThere is no universal “fastest” choice based only on the algorithm names. BFS and DFS have different exploration orders and can require different frontier space on a particular graph. UCS additionally orders candidates by path cost. Choose based on the goal and graph assumptions, then consider the graph’s size and shape when memory or runtime is important.
Quick Recap
Best Value
Common mistakes to avoid
- Using “shortest” without defining it: BFS minimizes edge count in an unweighted graph; UCS minimizes accumulated cost under its assumptions.
- Swapping a queue for a stack and expecting optimality: this changes the exploration order from BFS to DFS, but does not give DFS a shortest-path guarantee.
- Ignoring cycles: graph searches should track visited or discovered states to avoid processing the same nodes repeatedly.
- Assuming UCS uses a guess about the goal: UCS prioritizes the path cost already paid, g(n); it is not heuristic search.
- Forgetting whether the input is a tree or a graph, or whether edges have weights: these details affect what guarantee applies and how to choose.
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
