#include
#include
using namespace std;
struct node //the data structure for the nodes that are being explored
{
int data;
node *next;
};
class Queue //the data structure for the queue that is being used to store the nodes that are being searched
{
private:
node *front;
node *rear;
public:
Queue()
{
front = NULL;
rear = NULL;
}
~Queue()
{
delete front;
}
void display() //displays the nodes stored within the queue
{
node *p = new node();
p = front;
if(front == NULL)
cout << "\nNothing to display!" << endl;
else
{
while(p != NULL)
{
cout << "\n" << p->data << endl;
p = p->next;
}
}
}
void enqueue(int indata) //adds a new node to the queue
{
node *temp = new node();
temp->data = indata;
temp->next = NULL;
if(front == NULL)
front = temp;
else
rear->next = temp;
rear = temp;
}
int dequeue() //removes a node from the queue and returns the value of that node
{
node *temp = new node();
int tempdata;
if(front == NULL)
cout << "\nQueue is empty!" << endl;
else
{
temp = front;
tempdata = temp->data;
front = front->next;
delete temp;
}
return tempdata;
}
bool isEmpty() //returns whether the queue is empty or not
{
return (front == NULL);
}
};
class Graph //the data structure for the graph that is to be searched through
{
private:
int n; //# of vertices in graph
int **A; //stores the edge between two vertices
public:
Graph(int size) //allows for variable creation of initial nodes
{
if(size < 2)
n = 2;
else
n = size;
A = new int*[n];
for(int i = 0; i < n; i++)
A[i] = new int[n];
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
A[j][k] = 0;
}
~Graph()
{
for(int i = 0; i < n; i++)
delete [] A[i];
delete [] A;
}
bool isConnected(int u, int v) //returns whether the two nodes being checked are connected to each other in the graph
{
return (A[u-1][v-1] == 1);
}
void addEdge(int u, int v) //adds a connection between the two given nodes
{
A[u-1][v-1] = A[v-1][u-1] = 1;
}
void BFS(int s, int g) //the Breadth-First Search function for searching through the graph
{
Queue Q;
bool found = false; //denotes whether the goal node has been found
bool *explored = new bool[n+1]; //stores explored vertices
for(int i = 1; i <= n; i++) //initializes all vertices as unexplored
explored[i] = false;
Q.enqueue(s); //adds intial vertex
explored[s] = true;
cout << "BFS starting from vertex " << s << endl;
while(!Q.isEmpty() && !found)
{
int v = Q.dequeue();
cout << v << " ";
if(v == g) //stops the search after the goal node has been found
{
cout << "\n\nGoal found.";
found = true;
}
else
{
for(int w = 1; w <= n; w++)
{
if(isConnected(v, w) && !explored[w]) //enqueues the nodes that are connected to each other, in a FIFO order
{
Q.enqueue(w);
explored[w] = true;
}
}
}
}
cout << endl;
delete [] explored;
}
};
int main()
{
Graph g(12); //creates a graph with 12 nodes
g.addEdge(1, 2); //these edges can be changed and modified to make any graph
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 6);
g.addEdge(4, 7);
g.addEdge(5, 6);
g.addEdge(5, 7);
clock_t t1;
t1 = clock();
g.BFS(1, 3); //both tyhe root node and the goal node can be changed
float diff = (double)(clock() - t1)/CLOCKS_PER_SEC; //keeps track of the time taken for BFS
cout << endl << "Time taken for BFS: " << diff << endl;
return 0;
}