Understanding Search Algorithms: BFS, UCS, and DFS
Search algorithms are fundamental tools in computer science for exploring graphs and trees.
Let me explain three important ones in simple terms.
Breadth-First Search (BFS)
What it is: BFS explores all nodes at the present "depth level" before moving on to nodes at
the next depth level.
How it works:
Starts at the root node (or any starting node)
Explores all neighboring nodes first
Then moves to the next level neighbors
Uses a queue (First-In-First-Out) to keep track of nodes
Real-life analogy: Imagine searching for your keys at home:
1. First check all rooms on the first floor
2. Then go upstairs and check all rooms there
3. Finally check the basement
When to use:
When you want to find the shortest path in an unweighted graph
When the solution is likely close to the starting point
Example: Finding the shortest path in a maze where all moves have equal cost.
Algorithm:
🔍 Use: Finds the shortest path in unweighted graphs.
def BFS(start):
queue = [start] # Use a queue to explore level by level
visited = set([start]) # Keep track of visited nodes
while queue: # Loop until no nodes left
node = [Link](0) # Get the first node from the queue
print(node) # Process the node (could be checking goal)
for neighbor in [Link]:
if neighbor not in visited: # If we haven't seen this node yet
[Link](neighbor) # Mark it as visited
[Link](neighbor) # Add to the queue to explore later
Uniform-Cost Search (UCS)
What it is: UCS is a variant of BFS that considers path costs rather than depth.
How it works:
Expands the least-cost node first
Uses a priority queue ordered by path cost
Guarantees the cheapest path to each node
Real-life analogy: Choosing the cheapest travel route:
1. First consider all direct flights
2. Then consider flights with 1 connection if they're cheaper
3. Continue until you find the absolute cheapest option
When to use:
When actions have different costs
When you need the lowest-cost path in a weighted graph
Example: Finding the cheapest flight route between two cities.
Algorithm: Use: Finds the least-cost path in weighted graphs.
import heapq
def UCS(start):
queue = [(0, start)] # Priority queue: (cost_so_far, node)
visited = set()
while queue:
cost, node = [Link](queue) # Node with the lowest cost
if node in visited:
continue # Skip if we've already processed it
[Link](node)
print(node) # Process the node (could be checking goal)
for neighbor, step_cost in [Link]:
if neighbor not in visited:
total_cost = cost + step_cost
[Link](queue, (total_cost, neighbor)) # Add with updated cost
Depth-First Search (DFS)
What it is: DFS explores as far as possible along each branch before backtracking.
How it works:
Starts at the root node
Explores as far as possible along each branch
Backtracks when it reaches the end of a branch
Uses a stack (Last-In-First-Out) or recursion
Real-life analogy: Exploring a cave system:
1. Take the first passage you see
2. At each junction, pick a new passage
3. When you hit a dead end, backtrack to the last junction
When to use:
When the solution is likely far from the starting point
For topological sorting
When memory is limited (uses less memory than BFS)
Example: Solving a maze where you always turn right at junctions.
Algorithm: Use: Explores as deep as possible. Good for full traversal or puzzles.
def DFS(node, visited=set()):
print(node) # Process the node (could be checking goal)
[Link](node) # Mark as visited
for neighbor in [Link]:
if neighbor not in visited: # Go deeper if not visited
DFS(neighbor, visited) # Recursive call for the neighbor
Comparison Summary
Algorith
Order of Exploration Data Structure Best For
m
BFS Level by level Queue Shortest path (unweighted)
UCS Cheapest cost first Priority queue Lowest-cost path
DFS Deep then backtrack Stack Deep solutions, memory efficiency