fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <omp.h>
  5.  
  6. using namespace std;
  7.  
  8. // Graph class representing the adjacency list
  9. class Graph {
  10.     int V;  // Number of vertices
  11.     vector<vector<int>> adj;  // Adjacency list
  12.  
  13. public:
  14.     Graph(int V) : V(V), adj(V) {}
  15.  
  16.     // Add an edge to the graph
  17.     void addEdge(int v, int w) {
  18.         adj[v].push_back(w);
  19.     }
  20.  
  21.     // Parallel Depth-First Search
  22.     void parallelDFS(int startVertex) {
  23.         vector<bool> visited(V, false);
  24.         parallelDFSUtil(startVertex, visited);
  25.     }
  26.  
  27.     // Parallel DFS utility function
  28.     void parallelDFSUtil(int v, vector<bool>& visited) {
  29.         visited[v] = true;
  30.         cout << v << " ";
  31.  
  32.         #pragma omp parallel for
  33.         for (int i = 0; i < adj[v].size(); ++i) {
  34.             int n = adj[v][i];
  35.             if (!visited[n])
  36.                 parallelDFSUtil(n, visited);
  37.         }
  38.     }
  39.  
  40.     // Parallel Breadth-First Search
  41.     void parallelBFS(int startVertex) {
  42.         vector<bool> visited(V, false);
  43.         queue<int> q;
  44.  
  45.         visited[startVertex] = true;
  46.         q.push(startVertex);
  47.  
  48.         while (!q.empty()) {
  49.             int v = q.front();
  50.             q.pop();
  51.             cout << v << " ";
  52.  
  53.             #pragma omp parallel for
  54.             for (int i = 0; i < adj[v].size(); ++i) {
  55.                 int n = adj[v][i];
  56.                 if (!visited[n]) {
  57.                     visited[n] = true;
  58.                     q.push(n);
  59.                 }
  60.             }
  61.         }
  62.     }
  63. };
  64.  
  65. int main() {
  66.     // Create a graph
  67.     Graph g(7);
  68.     g.addEdge(0, 1);
  69.     g.addEdge(0, 2);
  70.     g.addEdge(1, 3);
  71.     g.addEdge(1, 4);
  72.     g.addEdge(2, 5);
  73.     g.addEdge(2, 6);
  74.  
  75.     /*
  76.         0 -------->1
  77.         |         / \
  78.         |        /   \
  79.         |       /     \
  80.         v       v       v
  81.         2 ----> 3       4
  82.         |      |
  83.         |      |
  84.         v      v
  85.         5      6
  86.     */
  87.  
  88.     cout << "Depth-First Search (DFS): ";
  89.     g.parallelDFS(0);
  90.     cout << endl;
  91.  
  92.     cout << "Breadth-First Search (BFS): ";
  93.     g.parallelBFS(0);
  94.     cout << endl;
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Depth-First Search (DFS): 0 1 3 4 2 5 6 
Breadth-First Search (BFS): 0 1 2 3 4 5 6
https://ideone.com/nTO6ra
language:
C++14 (gcc 8.3)
created:
17 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!