Breadth-First Search

Graph traversal algorithm that explores all nodes at the current depth level before moving to the next level, guaranteeing shortest path in unweighted graphs.

Family: Planning Algorithms Status: ✅ Complete

Need Help Understanding This Algorithm?

🤖 Ask ChatGPT about Breadth-First Search

Overview

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores nodes level by level,

visiting all nodes at distance k from the start before exploring nodes at distance k+1. This systematic approach guarantees that the first time a goal is reached, it's via the shortest path in unweighted graphs.

BFS is complete and optimal for unweighted graphs, making it ideal for problems where all edges have equal cost. It's widely used in shortest path problems, level-order tree traversal, and social network analysis.

Mathematical Formulation¶

🧮 Ask ChatGPT about Mathematical Formulation

Mathematical Properties

Level Order

L₀ = {start}, Lᵢ = {v : d(start, v) = i}

Nodes at distance i from start

Shortest Path

d(start, goal) = min{k : goal ∈ Lₖ}

Shortest path length in unweighted graph

Optimality

BFS finds path of length d(start, goal)

Guaranteed shortest path in unweighted graphs

Completeness

If path exists, BFS will find it

Algorithm is complete for finite graphs

Key Properties¶

🔑 Ask ChatGPT about Key Properties

Optimal for Unweighted

Finds shortest path in unweighted graphs
Complete

Guaranteed to find solution if one exists
Level-by-Level

Explores nodes in order of distance from start
Memory Intensive

Stores all nodes at current level

Implementation Approaches¶

💻 Ask ChatGPT about Implementation

Standard BFS Implementation

Classic BFS using queue data structure

Complexity:

Time: O(V + E)
Space: O(V)

Advantages

Guaranteed shortest path in unweighted graphs
Complete algorithm
Simple to implement
Level-by-level exploration
Good for tree traversal

Disadvantages

Memory intensive for large graphs
Not optimal for weighted graphs
May explore many unnecessary nodes
Requires storing all nodes at current level

Use Cases & Applications¶

🌍 Ask ChatGPT about Applications

Application Categories

Shortest Path

unweighted pathfinding: unweighted pathfinding
social network analysis: social network analysis
web crawling: web crawling

Tree Traversal

level-order traversal: level-order traversal
binary tree operations: binary tree operations
hierarchy processing: hierarchy processing

Graph Analysis

connected components: connected components
bipartite graph detection: bipartite graph detection
cycle detection: cycle detection

Puzzle Solving

sliding puzzles: sliding puzzles
maze solving: maze solving
word ladder: word ladder

Educational Value

Understanding graph traversal: Understanding graph traversal
Queue data structure usage: Queue data structure usage
Level-order processing: Level-order processing
Shortest path concepts: Shortest path concepts

References & Further Reading¶

:material-book: Core Textbooks

:material-file-document:

Interactive Learning

Try implementing the different approaches yourself! This progression will give you deep insight into the algorithm's principles and applications.

Pro Tip: Start with the simplest implementation and gradually work your way up to more complex variants.

Need More Help? Ask ChatGPT!

🧒 Explain Simply 📝 Practice Problems 🔀 Compare Algorithms 🐛 Debug Help

Related Algorithms in Planning Algorithms:

M* - Multi-agent pathfinding algorithm that finds collision-free paths for multiple agents by resolving conflicts and coordinating their movements.
A* Search - Optimal pathfinding algorithm that uses heuristics to efficiently find the shortest path from start to goal in weighted graphs.
Depth-First Search - Graph traversal algorithm that explores as far as possible along each branch before backtracking, using stack-based or recursive implementation.