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) : V(V) {
  14.         adj.resize(V);
  15.     }
  16.  
  17.     void addEdge(int u, int v) {
  18.         adj[u].push_back(v);
  19.     }
  20.  
  21.     void bfs(int start) {
  22.         vector<bool> visited(V, false);
  23.         queue<int> q;
  24.  
  25.         q.push(start);
  26.         visited[start] = true;
  27.  
  28.         while (!q.empty()) {
  29.             int current;
  30.  
  31.             #pragma omp parallel shared(q, visited) private(current)
  32.             {
  33.                 #pragma omp critical
  34.                 {
  35.                     current = q.front();
  36.                     q.pop();
  37.                 }
  38.  
  39.                 #pragma omp for
  40.                 for (int i = 0; i < adj[current].size(); ++i) {
  41.                     int neighbor = adj[current][i];
  42.  
  43.                     if (!visited[neighbor]) {
  44.                         #pragma omp critical
  45.                         {
  46.                             visited[neighbor] = true;
  47.                             q.push(neighbor);
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.     }
  54.  
  55.     void dfsUtil(int v, vector<bool>& visited) {
  56.         visited[v] = true;
  57.         cout << v << " ";
  58.  
  59.         #pragma omp parallel for
  60.         for (int i = 0; i < adj[v].size(); ++i) {
  61.             int u = adj[v][i];
  62.             if (!visited[u]) {
  63.                 dfsUtil(u, visited);
  64.             }
  65.         }
  66.     }
  67.  
  68.     void dfs(int start) {
  69.         vector<bool> visited(V, false);
  70.         dfsUtil(start, visited);
  71.     }
  72. };
  73.  
  74. int main() {
  75.     Graph g(6);
  76.     g.addEdge(0, 1);
  77.     g.addEdge(0, 2);
  78.     g.addEdge(1, 3);
  79.     g.addEdge(1, 4);
  80.     g.addEdge(2, 4);
  81.     g.addEdge(3, 5);
  82.     g.addEdge(4, 5);
  83.  
  84.     cout << "BFS starting from vertex 0: ";
  85.     g.bfs(0);
  86.     cout << endl;
  87.  
  88.     cout << "DFS starting from vertex 0: ";
  89.     g.dfs(0);
  90.     cout << endl;
  91.  
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BFS starting from vertex 0: 
DFS starting from vertex 0: 0 1 3 5 4 2
https://ideone.com/leOjiu
language:
C++14 (gcc 8.3)
created:
12 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!