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.
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!.