#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <omp.h>
using namespace std;
// Parallel BFS using OpenMP
void parallel_bfs(int start, vector<vector<int> >& graph, vector<int>& visited, int n) {
queue<int> q;
q.push(start);
visited[start] = 1;
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
#pragma omp parallel for
for (int i = 0; i < n; i++) {
if (graph[v][i]) {
#pragma omp critical
{
if (!visited[i]) {
visited[i] = 1;
q.push(i);
}
}
}
}
}
}
// Parallel DFS using OpenMP (iterative version)
void parallel_dfs(int start, vector<vector<int> >& graph, vector<int>& visited, int n) {
stack<int> s;
s.push(start);
visited[start] = 1;
while (!s.empty()) {
int v;
#pragma omp critical
{
v = s.top();
s.pop();
}
cout << v << " ";
#pragma omp parallel for
for (int i = 0; i < n; i++) {
if (graph[v][i]) {
#pragma omp critical
{
if (!visited[i]) {
visited[i] = 1;
s.push(i);
}
}
}
}
}
}
int main() {
int n, edges, u, v, start;
cout << "Enter number of vertices: ";
cin >> n;
vector<vector<int> > graph(n, vector<int>(n, 0));
vector<int> visited(n, 0);
cout << "Enter number of edges: ";
cin >> edges;
cout << "Enter the edges (u v):\n";
for (int i = 0; i < edges; i++) {
cin >> u >> v;
graph[u][v] = graph[v][u] = 1;
}
cout << "Enter starting vertex: ";
cin >> start;
int ch;
do {
cout << "\nMenu:\n";
cout << "1. Parallel BFS traversal\n";
cout << "2. Parallel DFS traversal\n";
cout << "3. Exit\n";
cout << "Enter your choice: ";
cin >> ch;
visited.assign(n, 0); // Reset visited before each run
switch (ch) {
case 1:
cout << "Parallel BFS traversal: ";
parallel_bfs(start, graph, visited, n);
cout << endl;
break;
case 2:
cout << "Parallel DFS traversal: ";
parallel_dfs(start, graph, visited, n);
cout << endl;
break;
case 3:
cout << "Exiting...\n";
break;
default:
cout << "Invalid choice. Try again.\n";
}
} while (ch != 3);
return 0;
}
Output:
C:\Users\Admin\Desktop\Final year\Practical code\LP-V HPC> g++ -fopenmp bfs.cpp -o bfs
C:\Users\Admin\Desktop\Final year\Practical code\LP-V HPC>.\bfs.exe
Enter number of nodes: 6
Enter number of edges: 7
Enter 7 edges (u v):
0 1
0 2
0 3
1 4
2 5
3 5
4 5
Enter start node for BFS/DFS: 0
Parallel BFS starting from node 0:
Thread 0 visiting 0
Thread 1 visiting 1
Thread 2 visiting 2
Thread 0 visiting 3
Thread 1 visiting 4
Thread 0 visiting 5
BFS Execution time: 0.0120001 seconds
Parallel DFS starting from node 0:
Thread 3 visiting 0
Thread 2 visiting 1
Thread 1 visiting 2
Thread 0 visiting 3
Thread 2 visiting 4
Thread 1 visiting 5
Thread 0 visiting 5
Thread 2 visiting 5
Thread 1 visiting 3
Thread 0 visiting 4
Thread 2 visiting 2
Thread 2 visiting 3
Thread 2 visiting 1
Thread 1 visiting 4
Thread 0 visiting 2
Thread 1 visiting 1
DFS Execution time: 0.0189998 seconds