BFS [ Breadth First Search ]

class BFS
{
    Graph* _graph;
    int _source;
    int* _parent;
    int* _level;
    int* _color;
    bool _bipartite;

    std::vector<int>* _bfsQueue;

    void init(int);
    void path_rec(int);
public:
    BFS(Graph*, int);
    ~BFS();

    void breadhFirstSearch();
    void printPath(int);
    void printDetails();
};

BFS::BFS(Graph* graph, int source)
{
    this->_graph = graph;
    this->init(source);
}

BFS::~BFS()
{
    delete[] this->_parent;
    delete[] this->_level;
    delete _bfsQueue;
}

void BFS::init(int source)
{
    this->_source = source;
    this->_bipartite = true;
    this->_parent = new int[this->_graph->getVertexCount()];
    this->_level = new int[this->_graph->getVertexCount()];
    this->_color = new int[this->_graph->getVertexCount()];
    this->_bfsQueue = new std::vector<int>();

    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        _parent[i] = _level[i] = _color[i] = -1;
    }
}

void BFS::path_rec(int destination)
{
    if (this->_source == destination)
        cout << this->_source << " ";
    else if (this->_parent[destination] == -1)
        cout << "no path";
    else
    {
        path_rec(this->_parent[destination]);
        cout << destination << " ";
    }
}

void BFS::breadhFirstSearch()
{
    std::queue<int> bfs_Q;
    this->_level[this->_source] = 0;
    this->_color[this->_source] = 0;
    bfs_Q.push(this->_source);
    // bfs_queue->push_back(this->_source);

    while (!bfs_Q.empty())
    {
        int node = bfs_Q.front();
        bfs_Q.pop();

        for (int i = 0; i < this->_graph->getVertexCount(); ++i)
        {
            if (this->_graph->hasEdgeBetween(node, i))
            { // both discovered and undiscovered
                if (this->_bipartite)
                { // bi-coloring checks
                    if (this->_color[i] == -1)
                    { // needs to be colored
                        if (this->_color[node] == 0)
                            this->_color[i] = 1;
                        else this->_color[i] = 0;
                    }
                    if (this->_color[node] == this->_color[i])
                    { // color checking with adjacent node
                        this->_bipartite = false;
                    }
                }
                if (this->_level[i] == -1) // level by level bfs
                { // only for not discovered
                    this->_level[i] = this->_level[node] + 1;
                    this->_parent[i] = node;
                    bfs_Q.push(i);
                    _bfsQueue->push_back(i);
                }
            }
        }
    }
}

void BFS::printPath(int destination)
{
    cout << "\nCost from " << this->_source << " to " << destination
        << ": " << this->_level[destination] << "\nPath: ";
    this->path_rec(destination);
    cout << endl;
}

void BFS::printDetails()
{
    cout << "\nConnected vertices with [" << this->_source << "] : ";
    for (int i = 0; i < this->_bfsQueue->size(); ++i)
    {
        cout << _bfsQueue->at(i) << " ";
    }
    cout << "\n-----------------------------\n";

    cout << "\nDetails:\n--------";
    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        cout << "\n==> Level / cost of node " << i << " is "
            << this->_level[i] << endl;
        cout << "==> Parent of node " << i << " is " << this->_parent[i]
            << endl;
        cout << "==> Path from " << this->_source << " to " << i << " : ";
        this->path_rec(i);
        cout << endl;
    }

    cout << "\n# Bi-Coloring Type: "
        << (_bipartite ? "Bipartite" : "Not-bipartite")
        << "\n-------------------\n";
}