#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int V = 5; static vector<string> vertices; static vector<vector<string>> adjacencyList; static bool visited[V]; static int level[V]; class BFS { public: int indexOf(string val, vector<string> v) { auto match = find(v.begin(), v.end(), val); if(match != v.end()) return match - v.begin(); else return -1; } void insertVertex(string vertex) { vertices.push_back(vertex); } void constructAdjacencyList(string vtx, string adjcVertex) { int vtxIndex = indexOf(vtx, vertices); adjacencyList.push_back(vector<string>()); adjacencyList[vtxIndex].push_back(adjcVertex); } void breadthFirstSearch(string source) { queue<int> que; int sourceIndex = indexOf(source, vertices); visited[sourceIndex] = true; que.push(sourceIndex); while (que.size() != 0) { sourceIndex = que.front(); que.pop(); for (string iter : adjacencyList[sourceIndex]) { string str = iter; int i = indexOf(str, vertices); if (visited[i] == false) { visited[i] = true; level[i] = level[sourceIndex] + 1; que.push(i); } } cout << vertices[sourceIndex] << " of level " << level[sourceIndex] << " --> "; } } }; int main() { BFS bfs; adjacencyList = vector<vector<string>>(); vertices = vector<string>(); // Insert Vertices bfs.insertVertex("a"); bfs.insertVertex("b"); bfs.insertVertex("c"); bfs.insertVertex("d"); bfs.insertVertex("e"); // Construct Adjacency List bfs.constructAdjacencyList("a", "b"); bfs.constructAdjacencyList("a", "c"); bfs.constructAdjacencyList("a", "d"); bfs.constructAdjacencyList("b", "a"); bfs.constructAdjacencyList("b" ,"e"); bfs.constructAdjacencyList("c", "a"); bfs.constructAdjacencyList("c", "d"); bfs.constructAdjacencyList("c", "e"); bfs.constructAdjacencyList("d", "a"); bfs.constructAdjacencyList("d" ,"c"); bfs.constructAdjacencyList("d", "e"); bfs.constructAdjacencyList("e", "b"); bfs.constructAdjacencyList("e", "c"); bfs.constructAdjacencyList("e", "d"); bfs.breadthFirstSearch("c"); }
Let's list out, what all do we need to support Breadth First Search Data Structure.
Now, let us see the above code.
We have a List to store the Vertices.
static vector<string> vertices;
We also have a doubly List to store the Adjacency List.
static vector<vector<string>> adjacencyList;
Similarly, we have a Queue defined inside the method breadthFirstSearch(...).
queue<int> que;
And, we have an array to store the Levels.
static int level[V];
And, there is a bool array to store the Vertices that are visited.
static bool visited[V];
So, the first thing we will do is, insert the Vertices to the vector<string> vertices List.
vertices = vector<string>(); bfs.insertVertex("a"); bfs.insertVertex("b"); bfs.insertVertex("c"); bfs.insertVertex("d"); bfs.insertVertex("e");
void insertVertex(string vertex) { vertices.push_back(vertex); }
void insertVertex(string vertex) is quite simple.
There is just one statement in it.
vertices.push_back(vertex);
It accepts string vertex as a parameter and adds it to the List, vertices.
The next thing we will do is, create an Adjacency List to track the Adjacent Vertices.
Let us take the example of vertex a, to explain the creation of Adjacency List.
As we have seen, a has three adjacent vertices(i.e. b, c and d). And we have used the constructAdjacencyList(...) method to construct the Adjacency Matrix.
bfs.constructAdjacencyList("a", "b"); bfs.constructAdjacencyList("a", "c"); bfs.constructAdjacencyList("a", "d");
void constructAdjacencyList(string vtx, string adjcVertex) { int vtxIndex = indexOf(vtx, vertices); adjacencyList.push_back(vector<string>()); adjacencyList[vtxIndex].push_back(adjcVertex); }
Although, the above method is explained in Adjacency List Code tutorial. I will give a brief explanation in this tutorial.
When a method call is made,
The variable vtx is assigned with value "a" and adjcVertex is assigned with "b".
Now, the first line,
int vtxIndex = indexOf(vtx, vertices);
Calculates the index/position of Vertex a using the indexOf(..) function.
int indexOf(string val, vector<string> v) { auto match = find(v.begin(), v.end(), val); if(match != v.end()) return match - v.begin(); else return -1; }
And as we can see the index a is 0.
Now, in the next line,
adjacencyList.push_back(vector<string>());
We are initialising the first row of the 2D List, adjacencyList.
But with what?
We are initialising it with a List new list<string>(),
adjacencyList.push_back(vector<string>());
So that the first row can hold the Adjacency List for vertex a.
Similarly, the second row should hold the Adjacency List for vertex b and so on.
And in this iteration, our target is to find out the first row(To create an Adjacency List for vertex a) and insert vertex b to it.
And the below code does that.
adjacencyList[vtxIndex].push_back(adjcVertex);
We get the index of vertex a
int vtxIndex = indexOf(vtx, vertices);
As we know vtx is a.
Then add adjcVertex(That contains vertex b) to the 0th index of adjacencyList.
adjacencyList[0].push_back("b");
And following it we form the Adjacency List.
Then we come across the most important method void breadthFirstSearch(string source) that performs the Breadth First Search (BFS).
void breadthFirstSearch(string source) { queue<int> que; int sourceIndex = indexOf(source, vertices); visited[sourceIndex] = true; que.push(sourceIndex); while (que.size() != 0) { sourceIndex = que.front(); que.pop(); for (string iter : adjacencyList[sourceIndex]) { string str = iter; int i = indexOf(str, vertices); if (visited[i] == false) { visited[i] = true; level[i] = level[sourceIndex] + 1; que.push(i); } } cout << vertices[sourceIndex] << " of level " << level[sourceIndex] << " --> "; } }
So, we are calling the method
bfs.breadthFirstSearch("c");
Passing the vertex c as source.
Below is the graph on which we had to perform a Breadth First Search (BFS).
To perform Breadth First Search (BFS), all we need is a List to keep track of Vertices. Which we have in place.
And, we need a 2D Adjacency List to keep a track of Adjacent Vertices. And we also have that in place.
We also need a bool array to keep a track of which all vertices are visited. Which we also have in place. All the values default to false.
Lastly, we need the integer array to store the Levels, that is initialised with 0.
Now, since we have everything in place. Let us understand the void breadthFirstSearch(...) method.
So, if we see the first line of the above method,
queue<int> que;
We have declared the Queue to maintain the order of Breadth First Search (BFS).
Next, we will try to find the index of the source vertex,
int sourceIndex = indexOf(source, vertices);
In this case our source vertex is c. i.e. We will start traversing the graph from c. And the index of vetex c is 2.
So, the next thing we will do is mark vertex c as visited. i.e. We will mark the position of Vertex c to true in the Visited Array.
visited[sourceIndex] = true;
And add the vertex c to the Queue.
queue.push_back(sourceIndex);
Next, we come to the while() loop, that will continue until the Queue is not empty.
while (que.size() != 0) { sourceIndex = que.front(); que.pop(); for (string iter : adjacencyList[sourceIndex]) { string str = iter; int i = indexOf(str, vertices); if (visited[i] == false) { visited[i] = true; level[i] = level[sourceIndex] + 1; que.push(i); } } cout << vertices[sourceIndex] << " of level " << level[sourceIndex] << " --> "; }
Inside the while() loop, we write the below statement to get the vertex c out of the Queue and get its index in sourceIndex.
sourceIndex = que.front(); que.pop();
The next task we do is, try finding the Adjacent Vertices of vertex c.
As we know the Adjacent Vertices of vertex c are,
To find the Adjacent Vertices of c, we have used the below for loop,
for (string iter : adjacencyList[sourceIndex])
And the for loop itself needs a little explanation.(HIDE THE BELOW POINTS UNDER DROPDOWN)
for (string iter : adjacencyList[sourceIndex])
adjacencyList[sourceIndex]
Moral of the story
iter variable of iter, stores the Adjacency List of vertex c in it.So, iter has the elements a, d and e in it.
Inside the for loop, firstly we collect the first element(i.e. a) of the Adjacency List of vertex c.
string str = iter;
As we know the variable str contains a. Now, it's time to check the index of a.
Which we have done in the next line.
int i = indexOf(str, vertices);
And found that the index of a is 0.
Then in the next few lines, we check, if we have visited vertex a or not. So we check in the visited[] array.
And find that visited[0] is set to false. So, we get into the below if condition.
if (visited[i] == false) { visited[i] = true; level[i] = level[sourceIndex] + 1; que.push(i); }
Firstly, we mark visited[0] to true. Then increase the level[] array by 1.
And finally add the vertex a to the Queue.
We keep on checking the adjacency lists of the individual vertices and continue the same process until the Queue is empty.