Breadth-First Search (BFS)

Learn Breadth-First Search (BFS)

Introduction

Breadth-first search, usually called BFS, is a graph traversal algorithm that explores a graph layer by layer.

It starts from one vertex. First, it visits the starting vertex. Then it visits all vertices that are one edge away. After that, it visits all vertices that are two edges away, then three edges away, and so on.

This layer order is the main reason BFS is important in competitive programming. In an unweighted graph, where every edge has the same cost, BFS finds the shortest distance from the starting vertex to every reachable vertex.

BFS appears in many standard graph problems: shortest paths with simple moves, grid problems, connected components, bipartite checking, and many other tasks where we need to spread through a graph step by step.

Problem or motivation

We are given an unweighted graph with $n$ vertices and $m$ edges. We are also given a starting vertex $s$.

For every vertex $i$, we need to print the minimum number of edges needed to reach $i$ from $$. If vertex cannot be reached from , we print .