fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <omp.h>
  5.  
  6. using namespace std;
  7.  
  8. class Graph {
  9.     int V;
  10.     vector<vector<int>> adj;
  11.  
  12. public:
  13.     Graph(int V) {
  14.         this->V = V;
  15.         adj.resize(V);
  16.     }
  17.  
  18.     void addEdge(int u, int v) {
  19.         adj[u].push_back(v);
  20.         adj[v].push_back(u);  // undirected graph
  21.     }
  22.  
  23.     void parallelBFS(int start) {
  24.         vector<bool> visited(V, false);
  25.         queue<int> q;
  26.  
  27.         visited[start] = true;
  28.         q.push(start);
  29.  
  30.         while (!q.empty()) {
  31.             int node = q.front();
  32.             q.pop();
  33.  
  34.             cout << node << " ";
  35.  
  36.             #pragma omp parallel for
  37.             for (int i = 0; i < adj[node].size(); i++) {
  38.                 int neighbor = adj[node][i];
  39.  
  40.                 if (!visited[neighbor]) {
  41.                     #pragma omp critical
  42.                     {
  43.                         if (!visited[neighbor]) {
  44.                             visited[neighbor] = true;
  45.                             q.push(neighbor);
  46.                         }
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.     }
  52. };
  53.  
  54. int main() {
  55.  
  56.     Graph g(6);
  57.  
  58.     g.addEdge(0,1);
  59.     g.addEdge(0,2);
  60.     g.addEdge(1,3);
  61.     g.addEdge(1,4);
  62.     g.addEdge(2,5);
  63.  
  64.     cout << "Parallel BFS Traversal:\n";
  65.     g.parallelBFS(0);
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Parallel BFS Traversal:
0 1 2 3 4 5
https://ideone.com/zoxiJ5
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!