Algorithm Graph BFS(Breadth First Search)

Bismillahir Rahmanir Rahim

A standard BFS implementation puts each vertex of the graph into one of two categories:

1.Visited

2.Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

1.Start by putting any one of the graph's vertices at the back of a queue.

2.Take the front item of the queue and add it to the visited list.

3.Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited 

list to the back of the queue.

4.Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover 

every vertex, we can also run the BFS algorithm on every node

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+9;

vector<int>g[N];

bool vis[N]; ///initially all elements are false

int dis[N];

void bfs(int node)

{

    queue<int>q;

    q.push(node);

    vis[node]=true;

    dis[node]=0;

    while(!q.empty())

    {

        int running= q.front();

        q.pop();

        for(int i=0; i<g[running].size(); i++)

            if(!vis[g[running][i]])

            {

                vis[g[running][i]]=true;

                dis[g[running][i]]=dis[running]+1;

                q.push(g[running][i]);

            }

    }

}

int main()

{

    int node,edge,a,b;

    cin>>node>>edge;

    while(edge--)

    {

        cin>>a>>b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    bfs(1);

    for(int i=1;i<=node;i++) cout<<"Distance from 1 to "<<i<<" = "<<dis[i]<<endl;

    return 0;

}