fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <omp.h>
  5.  
  6. using namespace std;
  7.  
  8. // Structure to represent a graph
  9. struct Graph {
  10.     int V; // Number of vertices
  11.     vector<vector<int>> adj; // Adjacency list
  12. };
  13.  
  14. // Breadth-First Search (BFS) Algorithm
  15. void parallelBFS(const Graph& graph, int start) {
  16.     vector<bool> visited(graph.V, false);
  17.     queue<int> q;
  18.     q.push(start);
  19.     visited[start] = true;
  20.  
  21.     while (!q.empty()) {
  22.         #pragma omp parallel
  23.         {
  24.             int current;
  25.             #pragma omp critical
  26.             {
  27.                 current = q.front();
  28.                 q.pop();
  29.             }
  30.  
  31.             #pragma omp for
  32.             for (int i = 0; i < graph.adj[current].size(); ++i) {
  33.                 int neighbor = graph.adj[current][i];
  34.                 if (!visited[neighbor]) {
  35.                     visited[neighbor] = true;
  36.                     #pragma omp critical
  37.                     {
  38.                         q.push(neighbor);
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. int main() {
  47.     Graph graph;
  48.     graph.V = 6;
  49.     graph.adj = {
  50.         {1, 2}, // Node 0 is connected to nodes 1 and 2
  51.         {0, 3, 4}, // Node 1 is connected to nodes 0, 3, and 4
  52.         {0, 5}, // Node 2 is connected to nodes 0 and 5
  53.         {1}, // Node 3 is connected to node 1
  54.         {1}, // Node 4 is connected to node 1
  55.         {2} // Node 5 is connected to node 2
  56.     };
  57.  
  58.     // Perform BFS from node 0
  59.     cout << "Breadth-First Search (BFS) starting from node 0:\n";
  60.     parallelBFS(graph, 0);
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Breadth-First Search (BFS) starting from node 0:
https://ideone.com/1qhSdc
language:
C++ (gcc 8.3)
created:
10 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!