...

/

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