...

/

Breadth-First Search - Implementation

Breadth-First Search - Implementation

Implement the breadth-first traversal.

We'll cover the following...

Implementation

Let’s look at the implementation of Breadth-First Search.

Press + to interact
#include <iostream>
#include <map>
#include <queue>
#include <list>
using namespace std;
template <typename T>
class Graph
{
map<T, list<T>> adjList;
public:
Graph()
{
}
void addEdge(T u, T v, bool bidir = true)
{
adjList[u].push_back(v);
if (bidir)
adjList[v].push_back(u);
}
void bfs(T source_node)
{
queue<T> q;
map<T, bool> visited;
q.push(source_node);
visited[source_node] = true;
while (!q.empty())
{
T node = q.front();
cout << node << " ";
q.pop();
for (int neighbor : adjList[node])
{
if (!visited[neighbor])
{
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
};
int main()
{
Graph<int> g;
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(0, 4);
g.addEdge(2, 4);
g.addEdge(2, 3);
g.addEdge(3, 5);
g.addEdge(3, 4);
g.bfs(0);
}

Explanation:

  • From lines 1 to 4, we import all the header files required.
  • On line 7, we define a template class in C++.

    Templates are powerful features of C++ that allow you to write generic programs. In simple terms, you can create a single function or a class to work with different data types using templates. ...

  • On line 10, we define our adjacency list.
  • On line 12, we define our constructor for the class.
  • On line 15, we define a function addEdge() which will accept the two vertices that need to be joined by an edge and also a boolean value that will determine whether the edge is