Basic bfs code in C++



 ///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///
///Abul Hasnat  Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh
#include<bits/stdc++.h>
using namespace std;
int vis[100000];
int dis[100000];
vector<int>vec[100000];
int source,nod=0;
queue<int>q;
void bfs(int s)
{
    vis[s]=1;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(int i=0; i<vec[nod].size(); i++)
        {
            int next=vec[nod][i];
            if(vis[next]==0)
            {
               vis[next]=1;
               dis[next]=dis[nod]+1;
               q.push(next);
            }
        }
    }
}
int main()
{

    int node,edge;
    cout<<" node and edge : "<<endl;
    cin>>node>>edge;
    for (int i=0; i<edge; i++)
    {
        int u,v;
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    int source;
    cout<<"source "<<endl;
    cin >> source;
    bfs(source);
    cout << "From node " << source << endl;
    for (int i=1; i<=node; i++)
    {
        cout <<"Distance of "<<i<<" is : "<< dis[i] << endl;
    }
}

 

No comments

Most View Post

Recent post

Codeforces Round 971 (Div. 4) 2009C. The Legend of Freya the Frog Solution

  Problem Link    https://codeforces.com/contest/2009/problem/C S olution in C++: /// Author : AH_Tonmoy #include < bits / stdc ++. h &g...

Powered by Blogger.