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.         #pragma omp parallel
  26.         {
  27.             #pragma omp single
  28.             {
  29.                 q.push(start);
  30.                 visited[start] = true;
  31.             }
  32.  
  33.             while (!q.empty()) {
  34.                 int u;
  35.  
  36.                 #pragma omp critical
  37.                 {
  38.                     u = q.front();
  39.                     q.pop();
  40.                 }
  41.  
  42.                 #pragma omp for
  43.                 for (int i = 0; i < adj[u].size(); ++i) {
  44.                     int v = adj[u][i];
  45.  
  46.                     if (!visited[v]) {
  47.                         #pragma omp critical
  48.                         {
  49.                             q.push(v);
  50.                             visited[v] = true;
  51.                         }
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.     }
  57.  
  58.     void dfsUtil(int v, vector<bool>& visited) {
  59.         visited[v] = true;
  60.         cout << v << " ";
  61.  
  62.         #pragma omp parallel for
  63.         for (int i = 0; i < adj[v].size(); ++i) {
  64.             int u = adj[v][i];
  65.             if (!visited[u]) {
  66.                 dfsUtil(u, visited);
  67.             }
  68.         }
  69.     }
  70.  
  71.     void dfs(int start) {
  72.         vector<bool> visited(V, false);
  73.         dfsUtil(start, visited);
  74.     }
  75. };
  76.  
  77. int main() {
  78.     Graph g(6);
  79.     g.addEdge(0, 1);
  80.     g.addEdge(0, 2);
  81.     g.addEdge(1, 3);
  82.     g.addEdge(1, 4);
  83.     g.addEdge(2, 4);
  84.     g.addEdge(3, 5);
  85.     g.addEdge(4, 5);
  86.  
  87.     cout << "BFS starting from vertex 0: ";
  88.     g.bfs(0);
  89.     cout << endl;
  90.  
  91.     cout << "DFS starting from vertex 0: ";
  92.     g.dfs(0);
  93.     cout << endl;
  94.  
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0s 5296KB
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/g3THl6
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!