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