jain12

BFS in graph

Apr 21st, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include<iostream>
  2. #include<list>
  3. #include<queue>
  4. using namespace std;
  5.  
  6. class graph{
  7.   public:
  8.       int v;
  9.       list<int> *adj;
  10.       graph(int vertex){
  11.         v=vertex;
  12.         adj=new list<int>[v];
  13.         }
  14.       void AddEdge(int v1,int v2){
  15.         adj[v1].push_back(v2);
  16.         }
  17.  
  18.       void BFS(int start){
  19.            bool visit[v];
  20.            for(int i=0;i<v;i++)
  21.                 visit[i]=false;
  22.            queue<int>q;
  23.            q.push(start);
  24.            visit[start]=true;
  25.            while(!q.empty()){
  26.               int temp=q.front();
  27.               q.pop();
  28.               cout<<temp<<" ";
  29.               list<int>::iterator t;
  30.               for(t=adj[temp].begin();t!=adj[temp].end();t++){
  31.                 if(visit[*t]==false){
  32.                     visit[*t]=true;
  33.                     q.push(*t);
  34.                     }
  35.                 }
  36.               }
  37.  
  38.            }
  39.  
  40.   };
  41.  
  42. int main(){
  43.     graph g(4);
  44.     g.AddEdge(0, 1);
  45.     g.AddEdge(0, 2);
  46.     g.AddEdge(1, 2);
  47.     g.AddEdge(2, 0);
  48.     g.AddEdge(2, 3);
  49.     g.AddEdge(3, 3);
  50.     cout << "Following is Breadth First Traversal"
  51.             " (starting from vertex 2) \n";
  52.     g.BFS(2);
  53.     return 0;
  54.     }
Add Comment
Please, Sign In to add comment