Breadth-First Search (BFS) Algorithm Tutorial

Breadth-First Search (BFS)

Breadth-First Search (BFS), also known as level-order traversal, is a graph traversal algorithm that explores vertices level by level. BFS guarantees the shortest path in unweighted graphs.

You start from a source vertex and visit all neighbors before moving to the next level. You use a queue to process vertices in the order they're discovered.

function bfs(graph, n, source):
    dist = array of size n, initialized to -1
    dist[source] = 0
    queue = empty queue
    queue.enqueue(source)

    while queue is not empty:
        u = queue.dequeue()
        for each neighbor v of u:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.enqueue(v)

    return dist

Shortest path guarantee: The first time you reach a vertex, you've taken the minimum number of edges.

Mark before enqueueing: If you forget to mark vertices as visited before enqueueing, you'll add the same vertex multiple times.

Applications: You use BFS for shortest path in unweighted graphs, web crawlers, social network friend suggestions, GPS navigation, and network broadcasting.

Time complexity: $O(V + E)$ where $V$ is vertices and $E$ is edges.

Space complexity: $O(V)$ for the distance array and queue.