Step by step · Python, C++ and Java

Breadth-first search, visualized step by step

Breadth-first search explores a graph in rings: the start vertex, then everything one edge away, then everything two edges away. That order is why BFS finds shortest paths in unweighted graphs.

How it works

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

start = "A"
visited = set()
queue = [start]
order = []

while queue:
    node = queue.pop(0)
    if node in visited:
        continue
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            queue.append(neighbor)

print(order)

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
    map<string, vector<string>> graph;
    graph["A"] = {"B", "C"};
    graph["B"] = {"A", "D"};
    graph["C"] = {"A", "E"};
    graph["D"] = {"B", "F"};
    graph["E"] = {"C", "F"};
    graph["F"] = {"D", "E"};

    string start = "A";
    set<string> visited;
    vector<string> queue;
    vector<string> order;
    queue.push_back(start);

    while (!queue.empty()) {
        string node = queue.front();
        queue.erase(queue.begin());
        if (visited.count(node)) {
            continue;
        }
        visited.insert(node);
        order.push_back(node);
        for (string neighbor : graph[node]) {
            if (!visited.count(neighbor)) {
                queue.push_back(neighbor);
            }
        }
    }

    for (string name : order) {
        cout << name << " ";
    }
    cout << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, List<String>> graph = new LinkedHashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D"));
        graph.put("C", Arrays.asList("A", "E"));
        graph.put("D", Arrays.asList("B", "F"));
        graph.put("E", Arrays.asList("C", "F"));
        graph.put("F", Arrays.asList("D", "E"));

        String start = "A";
        Set<String> visited = new LinkedHashSet<>();
        List<String> queue = new ArrayList<>();
        List<String> order = new ArrayList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            String node = queue.remove(0);
            if (visited.contains(node)) {
                continue;
            }
            visited.add(node);
            order.add(node);
            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                }
            }
        }

        System.out.println(order);
    }
}

How breadth-first search works

A queue holds the vertices waiting to be visited. Take one from the front; if it has already been visited, skip it; otherwise mark it, record it, and add its unvisited neighbours to the back. Because the queue is first-in, first-out, every vertex at distance k is processed before any vertex at distance k + 1.

The example graph has six vertices, A to F, stored as an adjacency list. Starting from A, BFS visits A, B, C, D, E, F.

What to watch for when it runs

The graph is drawn with visited vertices marked and the current one highlighted.
The queue is drawn as a queue — vertices join at the back and leave from the front.
F is queued twice, once from D and once from E; the visited check is what stops it being processed twice.

Time and space complexity

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

Every vertex is processed once and every edge looked at a constant number of times. Popping the front of a Python list is itself O(n); collections.deque makes it O(1).

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.

How breadth-first search works

What to watch for when it runs

Time and space complexity

Related visualizations

Stuck on your own version?