• Sign Up
• Login
• 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
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.

Top