Skip to main content

BFS of a graph

#include<bits/stdc++.h>
using namespace std;
class graph
{
    int v;
    list<int> *adj;
public:
    graph(int v)
    {
        this->v=v;
        adj=new list<int>[v];
    }
    void add_edge(int v,int w)
    {
        adj[v].push_back(w);
    }
    void bfs(int start);
};
void graph:: bfs(int start)
{
    bool *visited=new bool[v];
    for(int i=0;i<v;i++)
        visited[i]=false;
    visited[start]=true;
    list<int> queue;
    queue.push_back(start);
    while(!queue.empty())
    {
        int s=queue.front();
        cout<<s<<" ";
        queue.pop_front();
        for(auto it=adj[s].begin();it!=adj[s].end();it++)
        {
            if(visited[*it]==false)
            {
                visited[*it]=true;
                queue.push_back(*it);
            }
        }
    }
}
int main()
{
    int v;
    cout<<"Enter the number of vertices"<<endl;
    cin>>v;
    graph g(v);
    while(1)
    {
        int x,y;
        cout<<"Enter the nodes"<<endl;
        cin>>x>>y;
        g.add_edge(x,y);
        cout<<"Enter -1 to exit"<<endl;
        int t;
        cin>>t;
        if(t==-1)
            break;
    }
    cout<<"Enter the starting node"<<endl;
    int start;
    cin>>start;
    g.bfs(start);
    return 0;
}

Comments

Popular posts from this blog

DFS using a stack

#include<bits/stdc++.h> using namespace std; class graph {     int v;     list<int> *adj; public:     graph(int v)     {         this->v=v;         adj=new list<int>[v];     }     void add_edge(int v,int w)     {         adj[v].push_back(w);     }     void dfs(int start); }; void graph:: dfs(int start) {     bool *visited=new bool[v];     for(int i=0;i<v;i++)         visited[i]=false;     visited[start]=true;     stack<int> s;     s.push(start);     while(!s.empty())     {         int k=s.top();         s.pop();       ...

DFS of a graph

#include<bits/stdc++.h> using namespace std; class graph {     int v;     list<int> *adj; public:     graph(int v)     {         this->v=v;         adj=new list<int>[v];     }     void add_edge(int v,int w)     {         adj[v].push_back(w);     }     void dfs(int v);     void dfsSearch(int v,bool visited[]); }; void graph:: dfsSearch(int start,bool visited[]) {     visited[start]=true;     cout<<start<<" ";     for(auto itr=adj[start].begin();itr!=adj[start].end();itr++)     {         if (!visited[*itr])         {             dfsSearch(*itr,visited); ...