Skip to content

Commit 8202a15

Browse files
Create bfs.cpp
1 parent 293bef0 commit 8202a15

File tree

1 file changed

+87
-0
lines changed

1 file changed

+87
-0
lines changed

graphs/bfs.cpp

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
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+
}

0 commit comments

Comments
 (0)