SHARE
TWEET

Untitled

a guest Jul 17th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Program to print BFS traversal from a given
  2. // source vertex. BFS(int s) traverses vertices  
  3. // reachable from s.
  4. #include<iostream>
  5. #include <list>
  6.  
  7. using namespace std;
  8.  
  9. // This class represents a directed graph using
  10. // adjacency list representation
  11. class Graph
  12. {
  13.     int V;    // No. of vertices
  14.  
  15.     // Pointer to an array containing adjacency
  16.     // lists
  17.     list<int> *adj;    
  18. public:
  19.     Graph(int V);  // Constructor
  20.  
  21.     // function to add an edge to graph
  22.     void addEdge(int v, int w);  
  23.  
  24.     // prints BFS traversal from a given source s
  25.     void BFS(int s);  
  26. };
  27.  
  28. Graph::Graph(int V)
  29. {
  30.     this->V = V;
  31.     adj = new list<int>[V];
  32. }
  33.  
  34. void Graph::addEdge(int v, int w)
  35. {
  36.     adj[v].push_back(w); // Add w to v’s list.
  37. }
  38.  
  39. void Graph::BFS(int s)
  40. {
  41.     // Mark all the vertices as not visited
  42.     bool *visited = new bool[V];
  43.     for(int i = 0; i < V; i++)
  44.         visited[i] = false;
  45.  
  46.     // Create a queue for BFS
  47.     list<int> queue;
  48.  
  49.     // Mark the current node as visited and enqueue it
  50.     visited[s] = true;
  51.     queue.push_back(s);
  52.  
  53.     // 'i' will be used to get all adjacent
  54.     // vertices of a vertex
  55.     list<int>::iterator i;
  56.  
  57.     while(!queue.empty())
  58.     {
  59.         // Dequeue a vertex from queue and print it
  60.         s = queue.front();
  61.         cout << s << " ";
  62.         queue.pop_front();
  63.  
  64.         // Get all adjacent vertices of the dequeued
  65.         // vertex s. If a adjacent has not been visited,  
  66.         // then mark it visited and enqueue it
  67.         for (i = adj[s].begin(); i != adj[s].end(); ++i)
  68.         {
  69.             if (!visited[*i])
  70.             {
  71.                 visited[*i] = true;
  72.                 queue.push_back(*i);
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. // Driver program to test methods of graph class
  79. int main()
  80. {
  81.     // Create a graph given in the above diagram
  82.     Graph g(10);
  83.     g.addEdge(1, 2);
  84.     g.addEdge(1, 5);
  85.  
  86.     g.addEdge(2, 1);
  87.     g.addEdge(2, 3);
  88.     g.addEdge(2, 4);
  89.     g.addEdge(2, 5);
  90.     g.addEdge(2, 7);
  91.    
  92.     g.addEdge(3, 2);
  93.     g.addEdge(3, 8);
  94.  
  95.     g.addEdge(4, 2);
  96.  
  97.     g.addEdge(5, 1);
  98.     g.addEdge(5, 2);
  99.     g.addEdge(5, 6);
  100.     g.addEdge(5, 7);
  101.  
  102.     g.addEdge(6, 5);
  103.     g.addEdge(6, 9);
  104.  
  105.     g.addEdge(7, 2);
  106.     g.addEdge(7, 5);
  107.     g.addEdge(7, 8);
  108.  
  109.     g.addEdge(8, 3);
  110.     g.addEdge(8, 7);
  111.  
  112.  
  113.     cout << "Following is Breadth First Traversal "
  114.          << "(starting from vertex 2) \n";
  115.     g.BFS(2);
  116.  
  117.     return 0;
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top