Breadth-first search or traversal (BFS) of a graph

Breadth-first search (BFS) is a search or traversal algorithm of a Graph Data Structure. This algorithm uses a queue to process each incoming vertex and process in LIFO order. At each vertex pops from the queue it takes all not visited adjacent vertices into queue this process happens until the queue becomes empty.

Let’s see pictorial simulation of this algorithm with a simple 6 vertices 7 edges connected graph.

Starts with initial vertex “A” and pushes into queue at first position as 0(A).
Pop a vertex from queue and push all its edges {1, 3, 5} into queue then next pop is vertex “B”.
Next vertex pops from queue and its edges {5, 1} added in queue then next pop is vertex “D”
Pop next vertex “D” from queue and push its edges {1, 4} then next pop is vertex “F”
Now pops vertices {1, 5, 1} are already visited we are skipping those and next pop as vertex “E”.
Pop next vertex 4 from queue and add its edges {3, 5} in queue. And as vertices {0, 1} are already visited, they skipped then next pop is vertex “C”.
Finally, “C”s neighbor vertex 5 is pushes to queue and leftover elements in the queue are already visited, hence the loop ends so the BFS is {0, 1, 3, 5, 4, 2}.

Let’s see the coding part of this algorithm, as we already know it uses queue data structure to store edge vertices of visited vertex.

void Graph::BFSUtil(std::list<Vertex *> queue)
{
    while (!queue.empty())
    {
        Vertex *topVertex = queue.back();
        if (topVertex->isVisited)
        {
            queue.pop_back();
            continue;
        }
        topVertex->isVisited = true;
        queue.pop_back();
        cout << topVertex->data << "  ";
        vector<Vertex *>::iterator itr;
        for (itr = topVertex->edges->begin(); itr != topVertex->edges->end(); itr++)
        {
            Vertex *tmp = *itr;
            if (!tmp->isVisited)
            {
                queue.push_front(tmp);
            }
        }
    }
}

void Graph::BFS()
{
    std::list<Vertex *> queue;
    queue.push_front(vertices[0]);
    BFSUtil(queue);
    cout << endl;
}
// Output:
BFS is: 
0  1  3  5  4  2

Complexity: O(E*V)
Space: O(E*V)

The above code runs with complexity O(E*V) with a similar space. Complete code with driver code can be found here below.

Hence is the complete description and implementation of Breadth-first search or traversal (BFS). If you find any bugs or algorithms mistakes you can let readers know by commenting on your observation below, Cheers!.