Scribd
Upload
15 views3 pages

Parallel BFS and DFS in C++

The document contains C++ code to perform parallel breadth-first search (BFS) and depth-first search (DFS) on a graph using OpenMP. It defines functions for parallel BFS and DFS that take a start node, uses queues and visited arrays, and outputs the visited nodes.

Uploaded by

Dhanashri Salunkhe
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views3 pages

Parallel BFS and DFS in C++

The document contains C++ code to perform parallel breadth-first search (BFS) and depth-first search (DFS) on a graph using OpenMP. It defines functions for parallel BFS and DFS that take a start node, uses queues and visited arrays, and outputs the visited nodes.

Uploaded by

Dhanashri Salunkhe
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <iostream>

#include <vector>
#include <queue>
#include <omp.h>

using namespace std;

const int MAX_NODES = 100;

vector<int> graph[MAX_NODES];

void parallelBFS(int start) {


bool visited[MAX_NODES] = {false};
queue<int> q;

[Link](start);
visited[start] = true;

while (![Link]()) {
int current = [Link]();
[Link]();

#pragma omp parallel for


for (int i = 0; i < graph[current].size(); ++i) {
int neighbor = graph[current][i];
#pragma omp critical
{
if (!visited[neighbor]) {
[Link](neighbor);
visited[neighbor] = true;
}
}
}
}

cout << "BFS Visited Nodes: ";


for (int i = 0; i < MAX_NODES; ++i) {
if (visited[i]) {
cout << i << " ";
}
}
cout << endl;
}

void parallelDFS(int start, bool visited[]) {


visited[start] = true;

#pragma omp parallel for


for (int i = 0; i < graph[start].size(); ++i) {
int neighbor = graph[start][i];
if (!visited[neighbor]) {
parallelDFS(neighbor, visited);
}
}
}

int main() {
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0, 5, 6};
graph[3] = {1};
graph[4] = {1};
graph[5] = {2};
graph[6] = {2};

int start_node = 0;

parallelBFS(start_node);

bool visited[MAX_NODES] = {false};


parallelDFS(start_node, visited);

cout << "DFS Visited Nodes: ";


for (int i = 0; i < MAX_NODES; ++i) {
if (visited[i]) {
cout << i << " ";
}
}
cout << endl;

return 0;
}
OUTPUT******************
**************

PS C:\Users\DELL\OneDrive\Desktop\HPC> cd
"c:\Users\DELL\OneDrive\Desktop\HPC\" ; if ($?) { g++
[Link] -o parallelbfsdfs } ; if ($?) {
.\parallelbfsdfs }

BFS Visited Nodes: 0 1 2 3 4 5 6

DFS Visited Nodes: 0 1 2 3 4 5 6

PS C:\Users\DELL\OneDrive\Desktop\HPC>

You might also like