/* 21143 Tanmay Karmarkar Assignment-6
Graph implementation and DFS BFS search.
*/
#include <iostream>
#include<vector>
#include <list>
using namespace std;
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency
// lists
vector<list<int>> adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w);
// prints BFS traversal from a given source s
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj.resize(V);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
vector<bool> visited;
visited.resize(V,false);
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued
// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (auto adjecent: adj[s])
{
if (!visited[adjecent])
{
visited[adjecent] = true;
queue.push_back(adjecent);
}
}
}
}
int main()
{
Graph obj(10);
int v,w;
bool a = true;
int ch;
while (a)
{
cout << "1.Insert" << endl;
cout << "2.Search-DFS" << endl;
cout << "3.Search-BFS" << endl;
cout << "4.Exit" << endl;
cout << "Enter operation to be performed : ";
cin >> ch;
switch (ch)
{
case 1:
cout<<"Enter Initial vertex : ";
cin>>v;
cout<<"Enter Final vertex : ";
cin>>w;
obj.addEdge(v,w);
break;
case 2:
break;
case 3:
obj.BFS(0);
break;
case 4:
a = false;
break;
default:
cout << "Enter Valid operation\n";
break;
}
}
cout << "Thank You";
return 0;
}