Breadth First Search

Basic BFS

This also finds the shortest path from the source vertex in an unweighted graph.

void bfs_util(int src)
{
    fill(dist, dist+N, INF);
    fill(prev, prev+N, -1);
    queue<int> Q;
    Q.push(src);
    dist[src] = 0;
    while ( !Q.empty() ) {
        int v = Q.front(); Q.pop();
        for ( int to : G[v] ) {
            if ( dist[to] == INF ) {
                dist[to] = dist[v] + 1;
                prev[to] = v;
                Q.push(to);
            }
        }
    }
}

0-1 BFS

Generally, BFS can find the shortest path only when the graph is unweighted, but if the weights have a constraint that their values are either 0 or 1, then the shortest path can be found by a modified version of BFS, which is called "0-1 BFS".

void bfs01(int src)
{
    fill(dist, dist+N, INF);
    fill(prev, prev+N, -1);
    deque<int> Q;
    Q.push_front(src);
    dist[src] = 0;
    while ( !Q.empty() ) {
        int v = Q.front(); Q.pop_front();
        for ( auto to : G[v] ) {
            if ( dist[v] + to.w < dist[to.id] ) {
                dist[to.id] = dist[v] + to.w;
                if ( to.w == 1 )
                    Q.push_back(to.id);
                else if ( to.w == 0 )
                    Q.push_front(to.id);
            }
        }
    }
}