Solution and implementation for Q13 from Data Structures and Algorithms Laboratory (dsal).
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) {
V = vertices;
adjList.resize(V);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
void display() const {
cout << "Adjacency List:\n";
for (int i = 0; i < V; i++) {
cout << i << " -> ";
for (int neighbor : adjList[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
cout << "BFS Traversal: ";
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
void DFSUtil(int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}
void DFS(int start) {
vector<bool> visited(V, false);
cout << "DFS Traversal: ";
DFSUtil(start, visited);
cout << endl;
}
};
int main() {
Graph graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.display();
graph.BFS(0);
graph.DFS(0);
return 0;
}