Scribd
Upload
24 views2 pages

Parallel BFS Implementation in OpenMP

The document presents a C++ implementation of a parallel Breadth-First Search (BFS) algorithm using OpenMP. It includes functions for adding edges to a graph and performing BFS traversal, while ensuring thread safety with critical sections. The main function initializes a graph and demonstrates BFS starting from a specified vertex.

Uploaded by

siddartha.ps2067
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views2 pages

Parallel BFS Implementation in OpenMP

The document presents a C++ implementation of a parallel Breadth-First Search (BFS) algorithm using OpenMP. It includes functions for adding edges to a graph and performing BFS traversal, while ensuring thread safety with critical sections. The main function initializes a graph and demonstrates BFS starting from a specified vertex.

Uploaded by

siddartha.ps2067
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Practical

BFS In Parallel using OpenMP


#include <iostream>
#include <queue>
#include <vector>
#include <omp.h>

using namespace std;

void addEdge(vector<vector<int>>& adj, int u, int v){


adj[u].push_back(v);
adj[v].push_back(u);
}

void bfs(vector<vector<int>>& adj, int s){


queue<int> q;

vector<bool> visited([Link](), false);


visited[s] = true;
[Link](s);

while(![Link]()){
int curr = [Link]();
[Link]();
cout << curr << " ";

#pragma omp parallel for


for(int i = 0; i < adj[curr].size(); i++){
int x = adj[curr][i];
if(!visited[x]){
#pragma omp critical
{
if (!visited[x]) {
visited[x] = true;
[Link](x);
}
}
}
}
}
}

int main(){
int V = 5;

vector<vector<int>> adj(V);

addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 2, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 4);

cout << "BFS starting from 0 : \n";


bfs(adj, 0);

return 0;
}

Output

You might also like