Breadth-First Search (BFS)

DSA · Graphs

Theory

BFS explores a graph level by level: it visits the start vertex, then all its neighbours, then their neighbours, using a queue and a visited set. Because it expands in rings of increasing distance, the first time BFS reaches a vertex is via the fewest edges, so it finds shortest paths in unweighted graphs. It runs in O(V + E) time.

Why we use it

BFS gives the shortest number of steps between nodes and explores closest options first.

When to use it

Use BFS for shortest paths in unweighted graphs or grids, degrees of separation, spreading processes (rotting oranges), and level-by-level exploration.

How it works

  1. queue = [start], visited = {start}
  2. Queue empty? Yes: Done. No: u = pop front, visit u.
  3. For each neighbour v of u
  4. v not visited? Yes: Mark visited, push v. No: Skip.
  5. Visits in order of distance (fewest edges)

Syntax

queue = deque([start]); visited = {start}
while queue:
    v = queue.popleft()
    for nb in graph[v]:
        if nb not in visited:
            visited.add(nb); queue.append(nb)

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

Example

from collections import deque

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}

def bfs_shortest(start, goal):
    q = deque([[start]])
    visited = {start}
    while q:
        path = q.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(path + [nb])
    return None

print("Shortest path A to F:", " -> ".join(bfs_shortest("A", "F")))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic