Breadth-first search

BFS explores a graph in layers. In an unweighted graph, these layers are shortest-path distances.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Set all distances to -1, then set the source distance to 0.
2. Use a queue: process the oldest discovered vertex first.
3. When a neighbor is first discovered, assign its distance and enqueue it.
4. First discovery is shortest because every earlier layer has already been processed.
5. The queue is FIFO; distance -1 is the undiscovered marker. Marking before enqueueing ensures each vertex enters the queue once.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
vector<int>bfs(const vector<vector<int>>&g,int s){
    vector<int>d(g.size(),-1);
    queue<int>q;
    q.push(s);
    d[s]=0;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int u:g[v]){
            if(d[u]==-1){
                d[u]=d[v]+1; // Mark before enqueueing.
                q.push(u);
            }
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source,target;
    cin>>n>>m>>source>>target;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int>distance=bfs(graph,source);
    cout<<distance[target]<<'\n';
}

Complexity analysis

O(V + E) time, O(V) auxiliary space.

Example input and output

Read n m source target, then m undirected unweighted edges. All labels are in 1..n, n≥1. Print the minimum number of edges, or -1 if the target is unreachable.

Input

5 3 1 3
1 2
2 3
4 5

Output

2

BFS reaches 2 in layer one and 3 in layer two. Vertices 4 and 5 are in a different component.

Practical applications

Use BFS for unweighted shortest paths, layers, and reachability. Dijkstra is needed for general nonnegative costs.

Check your understanding

Which container makes BFS explore in layers?

Put it into practice

Find the minimum number of edges between two given vertices; print -1 if unreachable.