Search⌘ K
AI Features

Breadth-First Search - Implementation

Explore how to implement Breadth-First Search (BFS) in C++ using template classes and adjacency lists. Learn to traverse graphs efficiently with BFS by managing visited nodes and queues, including coding and complexity details.

We'll cover the following...

Implementation

Let’s look ...

C++
#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
...