Breadth-first search

Explore a graph in rings: all neighbours first, then their neighbours. Finds shortest paths when every edge costs the same.

Time O(V + E)Space O(V)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

The queue processes nodes in the order they were discovered, so nodes one edge away come out before nodes two edges away, and so on.

Code

C++PythonC#

void bfs(unordered_map<char, vector<char>>& graph, char start) {
    unordered_set<char> seen{start};
    queue<char> q;
    q.push(start);
    while (!q.empty()) {
        char u = q.front(); q.pop();
        for (char v : graph[u])
            if (seen.insert(v).second) q.push(v);
    }
}

from collections import deque

def bfs(graph: dict[str, list[str]], start: str) -> None:
    seen = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in seen: seen.add(v); queue.append(v)

public static void Bfs(Dictionary<char, List<char>> graph, char start) {
    var seen = new HashSet<char> { start };
    var queue = new Queue<char>();
    queue.Enqueue(start);
    while (queue.Count > 0) {
        char u = queue.Dequeue();
        foreach (char v in graph[u])
            if (seen.Add(v)) queue.Enqueue(v);
    }
}

Tips

Mark a node as seen when you add it to the queue, not when you take it out. Otherwise it can be queued several times.
Use it for fewest moves, shortest path in a grid, and level-by-level problems.

In the .NET library

HashSet<T>.Add returns false when the item is already present, so "check and mark" is a single call.