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