#include <iostream>
#include <ctime>
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;
}