BFS_Algorithm.cpp

#include<bits/stdc++.h>
using namespace std;

#define WHITE 0
#define GRAY  1
#define BLACK 2
#define SIZE 100

int adj[SIZE];
int color[SIZE];
int parent[SIZE];
int dis[SIZE];

void bfs(int adj[][SIZE], int vertex, int starting_Node);
void print_path(int starting_Node, int end_Node);

int main()
{
    // queue int<q>;
    //q.push(1);
    //q.push(2);
    //cout << q.empty() <<endl;

    freopen("input.text", "r", stdin);

    int vertex;
    int edges;

    cin >> vertex >> edges;

    cout << "Vertex is: " << vertex <<endl;
    cout << "Edges: " << edges <<endl;

    int node1, node2;

    for (int i = 0; i < edges; i++)
    {
        // cout << "Enter 2 nodes: " <<endl;

        cin >> node1 >> node2;

        adj [node1][node2] = 1;
        adj [node2][node1] = 1;

    }

    for (int i = 0; i < vertex; i++)
    {
        for (int j = 0; j < vertex; j++)
        {
            cout << adj[i][j] << " ";
        }
        cout <<endl;
    }

    bfs(adj, vertex, 0)
    cout <endl;
    print_path(0, 7);

    void bfs(int adj[][SIZE], int vertex, int starting_Node)
    {
        for (int i = 0; i < vertex; i++)
        {
            if (i != starting_Node)
            {
                color[i] = WHITE;
                dis[i] = INT_MIN; //infinity
                parent[i] = -1;   //NULL
            }
        }
    }

    color(starting_Node) = GRAY;
    dis(starting_Node) = 0;
    parent (starting_Node) = -1; //NUlL;
    queue <int> bfs_queue;
    bfs_queue.push(starting_Node);

    cout << "BFS_queue is: ";

    while(!bfs_queue.empty())
    {
        int u = bfs_queue.front();
        cout << u << " ";
        bfs_queue.pop();

        for (int i = 0; i < vertex; i++)
        {
            if(adj[u][i] != 0)
            {
                int v = i;
                if (color[v] == WHITE)
                {
                    color[v] = GRAY;
                    dis[v] = dis[u] + 1;
                    parent[v] = u;
                    // cout << "Parent of << v << "is: " << parent[v];

                    bfs_queue.push(v);
                }
            }

        }

        color[u] = BLACk;
    }
}

void print_path(int string_Node, int end_Node)
{
    char path[SIZE];
    int par = parent[end_Node];
    path[i++] = end_Node+ '0';
    path[i++] = ' ';

    while (parent != -1)
    {
        path[i++] = par+'0';
        path[i++] = ' ';
        par = parent[par];

        //cout << "Par is: " << par <<endl;
        //if (i == 10);
        // break;
    }

    path[i] = '\0';
    strrev(path);
    cout << "Path is: " << path <<endl;
}