BFS

BFS
Runtime	O(V+E)
Class	Graph Algorithm

Breadth-first search (BFS) is a graph traversal algorithm.

Approach

At the core of BFS is a priority queue of unvisited nodes.

1. At the start, the source node has a distance of 0, whereas the rest has infinite distance. The source node is pushed into the queue.
2. The queue is popped as the first node in the queue is visited.
3. Upon visiting a node, if the node's distance is infinity (i.e. it hasn't been visited and isn't in the queue), BFS adds the node to the queue.
4. The next node is popped and visited until no nodes remain.

Implementation

BFS(G, s):
    # Initialize
    n = len(V)
    let Q be a FIFO queue
    let d be distance array of length n
    for each vertex u in V:
        d[u] = infty
    d[s] = 0
    Q.enqueue(s);

    while Q is not empty:
        visiting = Q.pop();
        for each node in adj[visiting]:
            if d[node] = infty:
                d[node] = d[visiting] + 1
                Q.enqueue(node)

Analysis

Since the nodes only enter the queue when their distance is infinity, and their distance gets updated as they enter the queue, each node only enters the queue once. O(V).

Inside each iteration, the adjacency list of each node is looked at, which takes O(E).

Therefore, the overall runtime complexity would be O(V + E).

Application

BFS is one solution to the shortest path problem. Given an unweighted graph, BFS can find the shortest number of jumps from one node to every other node (the distance array being kept track of). Notably, BFS does not work for weighted graphs due to each edge not being valued the same.