• API
• FAQ
• Tools
• Archive
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
11. class Graph
12. {
13.     int V;    // No. of vertices
14.
15.     // Pointer to an array containing adjacency
16.     // lists
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;
32. }
33.
34. void Graph::addEdge(int v, int w)
35. {
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
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);
85.
91.
94.
96.
101.
104.
108.