Multi Source BFS

In normal BFS, there is a single starting node (or source) which is pushed inside the queue from where we start traversing other nodes until the queue is not empty. Whereas in multi source BFS, we have multiple starting nodes, all of which are initially pushed into the queue and then traversal is started.

Let us consider an example of normal BFS

Given above graph, we have to find the distance between source node 1 and destination node 4.

Here's the simple BFS solution that works in O(n) time.

    #include<bits/stdc++.h>

    using namespace std;

    int distBetween(vector<int>*adj,int n,int src,int dest){

        queue<pair<int,int>>q;

        int d=0;

        q.push({src,d});

        vector<int>vis(n+1);

        while(!q.empty()){

            src=q.front().first;

            d=q.front().second;

            q.pop();

            if(vis[src])continue;

            vis[src]=1;

            if(src==dest)return d;

            for(auto &v:adj[src])

                q.push({v,d+1});

        }

        return -1;

    }

    int main(){

        system("CLS");

        int n=6;

        vector<int>adj[n+1];

        adj[1]={3,5};

        adj[2]={3,6};

        adj[3]={1,2,4,5,6};

        adj[4]={3,6};

        adj[5]={1,3,6};

        adj[6]={2,3,4,5};

        int src=1, dest=6;

        cout<<distBetween(adj,n,src,dest);

        return 0;

    };

Now, let consider a new problem. Among the nodes 1, 3 and 5, what is the closest distance from node 2?

Naive solution to this problem is to use a BFS for each given source nodes and find distance of them from destination node and return the minimum distance.

Time complexity will be O(number of nodes * BFS time for each node)

In worst case, number of nodes can be n (where n is the number of nodes in the graph), in this case time complexity will be O(n*n).

    #include<bits/stdc++.h>

    using namespace std;

    int distBetween(vector<int>*adj,int n,int src,int dest){

        queue<pair<int,int>>q;

        int d=0;

        q.push({src,d});

        vector<int>vis(n+1);

        while(!q.empty()){

            src=q.front().first;

            d=q.front().second;

            q.pop();

            if(vis[src])continue;

            vis[src]=1;

            if(src==dest)

                return d;

            for(auto &v:adj[src])

                q.push({v,d+1});

        }

        return -1;

    }

    int main(){

        system("CLS");

        int n=6;

        vector<int>adj[n+1];

        adj[1]={3,5};

        adj[2]={3,6};

        adj[3]={1,2,4,5,6};

        adj[4]={3,6};

        adj[5]={1,3,6};

        adj[6]={2,3,4,5};

        int src1=1,src2=3,src3=5, dest=6;

        cout<<min({distBetween(adj,n,src1,dest),

                   distBetween(adj,n,src2,dest),

                   distBetween(adj,n,src3,dest)});

        return 0;

    };

Efficient solution: Using multi source BFS.

It is similar to normal BFS, but unlike normal BFS, we push all the source nodes to the queue before starting the traversal.

Time complexity: O(n)

    #include<bits/stdc++.h>

    using namespace std;

    int distBetween(vector<int>*adj,int n,vector<int>&src,int dest){

       

        queue<pair<int,int>>q;

        int d=0;

        for(auto &s:src)

            q.push({s,d});

        vector<int>vis(n+1);

        while(!q.empty()){

            int s=q.front().first;

            d=q.front().second;

            q.pop();

            if(vis[s])continue;

            vis[s]=1;

            if(s==dest)

                return d;

            for(auto &v:adj[s])

                q.push({v,d+1});

        }

        return -1;

    }

    int main(){

        system("CLS");

        int n=6;

        vector<int>adj[n+1];

        adj[1]={3,5};

        adj[2]={3,6};

        adj[3]={1,2,4,5,6};

        adj[4]={3,6};

        adj[5]={1,3,6};

        adj[6]={2,3,4,5};

        int dest=6;

        vector<int>src={1,2,3};

        cout<<distBetween(adj,n,src,dest);

        return 0;

    };

---

Related problems

1. 01 Matrix

2.Distance of nearest cell having 1

3.As Far from Land as Possible

Flood Fill Algorithm

 Flood Fill Algorithm

Flood fill algorithm helps in visiting each and every point in a given area. It determines the area connected to a given cell in a multi-dimensional array. Following are some famous implementations of flood fill algorithm:

Bucket Fill in Paint:
Clicking in an area with this tool selected fills that area with the selected color.

Solving a Maze:
Given a matrix with some starting point, and some destination with some obstacles in between, this algorithm helps to find out the path from source to destination

Minesweeper:
When a blank cell is discovered, this algorithm helps in revealing neighboring cells. This step is done recursively till cells having numbers are discovered.

Flood fill algorithm can be simply modeled as graph traversal problem, representing the given area as a matrix and considering every cell of that matrix as a vertex that is connected to points above it, below it, to right of it, and to left of it and in case of 8-connections, to the points at both diagonals also. For example, consider the image given below.

It clearly shows how the cell in the middle is connected to cells around it. For instance, there are 8-connections like there are in Minesweeper (clicking on any cell that turns out to be blank reveals 8 cells around it which contains a number or are blank). The cell (1,1) is connected in (2,1), (1,2), (1,0), (0,0), (0,2), (2,0), (2,2) and (0,1). 

ie Each (x,y) cell is connected to (x-1,y), (x+1,y), (x,y+1), (x,y-1), (x+1,y+1), (x+1,y-1), (x-1,y+1) and (x-1,y-1).

Algorithm

function DFS(x, y, visited, n, m)
    if (x ≥ n OR y ≥ m)
        return
    if(x < 0 OR y < 0)
        return
    if(visisted[x][y] == True)
        return
    visited[x][y] = True
    DFS(x-1, y-1, visited, n, m)
    DFS(x-1, y, visited, n, m)
    DFS(x-1, y+1, visited, n, m)
    DFS(x, y-1, visited, n, m)
    DFS(x, y+1, visited, n, m)
    DFS(x+1, y-1, visited, n, m)
    DFS(x+1, y, visited, n, m)
    DFS(x+1, y+1, visited, n, m)

The above code visits each and every cell of a matrix of size $n\times m$ starting with some source cell. Time Complexity of above algorithm is O(m*n).

Click here to see the demonstration of Flood Fill Algorithm