## C++, graph, breadth_first_search.cpp

``````/**
*
* \file
* \brief [Breadth First Search Algorithm
*
* \author [Ayaan Khan](https://github.com/ayaankhan98)
* \author [Aman Kumar Pandey](https://github.com/gpamangkp)
*
*
* \details
* Breadth First Search also quoted as BFS is a Graph Traversal Algorithm.
* Time Complexity O(|V| + |E|) where V are the number of vertices and E
* are the number of edges in the graph.
*
* Applications of Breadth First Search are
*
* 1. Finding shortest path between two vertices say u and v, with path
*    length measured by number of edges (an advantage over depth first
*    search algorithm)
* 2. Ford-Fulkerson Method for computing the maximum flow in a flow network.
* 3. Testing bipartiteness of a graph.
* 4. Cheney's Algorithm, Copying garbage collection.
*
* And there are many more...
*
* <h4>working</h4>
* In the implementation below we first created a graph using the adjacency
* list representation of graph.
* Breadth First Search Works as follows
* it requires a vertex as a start vertex, Start vertex is that vertex
* from where you want to start traversing the graph.
* We maintain a bool array or a vector to keep track of the vertices
* which we have visited so that we do not traverse the visited vertices
* again and again and eventually fall into an infinite loop. Along with this
* boolen array we use a Queue.
*
* 1. First we mark the start vertex as visited.
* 2. Push this visited vertex in the Queue.
* 3. while the queue is not empty we repeat the following steps
*
*      1. Take out an element from the front of queue
*      2. Explore the adjacency list of this vertex
*         if element in the adjacency list is not visited then we
*         push that element into the queue and mark this as visited
*
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <string>
#include <vector>

/**
* \namespace graph
* \brief Graph algorithms
*/
namespace graph {
/* Class Graph definition */
template <typename T>
class Graph {
/**
*  adjacency_list maps every vertex to the list of its neighbours in the
* order in which they are added.
*/
std::map<T, std::list<T> > adjacency_list;

public:
Graph() = default;
;
void add_edge(T u, T v, bool bidir = true) {
/**
*  add_edge(u,v,bidir) is used to add an edge between node u and
* node v by default , bidir is made true , i.e graph is
* bidirectional . It means if edge(u,v) is added then u-->v  and
* v-->u both edges exist.
*
*  to make the graph unidirectional pass the third parameter of
* add_edge as false which will
*/
if (bidir == true) {
// if graph is bidirectional
}
}

/**
*  this function performs the breadth first search on graph and return a
*  mapping which maps the nodes to a boolean value representing whether the
*  node was traversed or not.
*/
std::map<T, bool> breadth_first_search(T src) {
/// mapping to keep track of all visited nodes
std::map<T, bool> visited;
/// initialise every possible vertex to map to false
/// initially none of the vertices are unvisited
for (auto const &adjlist : adjacency_list) {
for (auto const &node : adjacency_list[adjlist.first]) {
visited[node] = false;
}
}

/// queue to store the nodes which are yet to be traversed
std::queue<T> tracker;

/// push the source vertex to queue to begin traversing
tracker.push(src);
/// mark the source vertex as visited
visited[src] = true;
while (!tracker.empty()) {
/// traverse the graph till no connected vertex are left
/// extract a node from queue for further traversal
T node = tracker.front();
/// remove the node from the queue
tracker.pop();
for (T const &neighbour : adjacency_list[node]) {
/// check every vertex connected to the node which are still
/// unvisited
if (!visited[neighbour]) {
/// if the neighbour is unvisited , push it into the queue
tracker.push(neighbour);
/// mark the neighbour as visited
visited[neighbour] = true;
}
}
}
return visited;
}
};
/* Class definition ends */
}  // namespace graph

/** Test function */
static void tests() {
/// Test 1 Begin
graph::Graph<int> g;
std::map<int, bool> correct_result;
correct_result = true;
correct_result = true;
correct_result = true;
correct_result = true;

std::map<int, bool> returned_result = g.breadth_first_search(2);

assert(returned_result == correct_result);
std::cout << "Test 1 Passed..." << std::endl;

/// Test 2 Begin

assert(returned_result == correct_result);
std::cout << "Test 2 Passed..." << std::endl;

/// Test 3 Begins
graph::Graph<std::string> g2;

std::map<std::string, bool> correct_res;
std::map<std::string, bool> returned_res =
correct_res["Gorakhpur"] = false;
correct_res["Lucknow"] = false;
correct_res["Kanpur"] = true;
correct_res["Agra"] = true;
correct_res["Prayagraj"] = false;
correct_res["Noida"] = true;
assert(correct_res == returned_res);
std::cout << "Test 3 Passed..." << std::endl;
}

/** Main function */
int main() {
tests();
size_t edges = 0;
std::cout << "Enter the number of edges: ";
std::cin >> edges;

graph::Graph<int> g;

std::cout << "Enter space-separated pairs of vertices that form edges: "
<< std::endl;
while (edges--) {
int u = 0, v = 0;
std::cin >> u >> v;