File tree Expand file tree Collapse file tree 1 file changed +87
-0
lines changed Expand file tree Collapse file tree 1 file changed +87
-0
lines changed Original file line number Diff line number Diff line change
1
+ #include < iostream>
2
+ #include < list>
3
+
4
+ using namespace std ;
5
+
6
+ class Graph
7
+ {
8
+ int V; // No. of vertices
9
+
10
+ // Pointer to an array containing adjacency
11
+ // lists
12
+ list<int > *adj;
13
+ public:
14
+ Graph (int V); // Constructor
15
+
16
+ // function to add an edge to graph
17
+ void addEdge (int v, int w);
18
+
19
+ // prints BFS traversal from a given source s
20
+ void BFS (int s);
21
+ };
22
+
23
+ Graph::Graph (int V)
24
+ {
25
+ this ->V = V;
26
+ adj = new list<int >[V];
27
+ }
28
+
29
+ void Graph::addEdge (int v, int w)
30
+ {
31
+ adj[v].push_back (w); // Add w to v’s list.
32
+ }
33
+
34
+ void Graph::BFS (int s)
35
+ {
36
+ // Mark all the vertices as not visited
37
+ bool *visited = new bool [V];
38
+ for (int i = 0 ; i < V; i++)
39
+ visited[i] = false ;
40
+
41
+ // Create a queue for BFS
42
+ list<int > queue;
43
+
44
+ // Mark the current node as visited and enqueue it
45
+ visited[s] = true ;
46
+ queue.push_back (s);
47
+
48
+ // 'i' will be used to get all adjacent
49
+ // vertices of a vertex
50
+ list<int >::iterator i;
51
+
52
+ while (!queue.empty ())
53
+ {
54
+ // Dequeue a vertex from queue and print it
55
+ s = queue.front ();
56
+ cout << s << " " ;
57
+ queue.pop_front ();
58
+
59
+ // Get all adjacent vertices of the dequeued
60
+ // vertex s. If a adjacent has not been visited,
61
+ // then mark it visited and enqueue it
62
+ for (i = adj[s].begin (); i != adj[s].end (); ++i)
63
+ {
64
+ if (!visited[*i])
65
+ {
66
+ visited[*i] = true ;
67
+ queue.push_back (*i);
68
+ }
69
+ }
70
+ }
71
+ }
72
+
73
+ int main ()
74
+ {
75
+ // Sample graph
76
+ Graph g (4 );
77
+ g.addEdge (0 , 1 );
78
+ g.addEdge (0 , 2 );
79
+ g.addEdge (1 , 2 );
80
+ g.addEdge (2 , 0 );
81
+ g.addEdge (2 , 3 );
82
+ g.addEdge (3 , 3 );
83
+ cout << " Following is Breadth First Traversal "
84
+ << " (starting from vertex 2) \n " ;
85
+ g.BFS (2 );
86
+ return 0 ;
87
+ }
You can’t perform that action at this time.
0 commit comments