Scribd
Upload
21 views3 pages

HPCPractical 2

The document contains two C++ programs that implement parallel breadth-first search (BFS) and depth-first search (DFS) algorithms using OpenMP for graph traversal. Both programs read a graph's edges, perform the respective search starting from a specified node, and output the visited nodes. The BFS and DFS implementations utilize OpenMP directives to parallelize the processing of adjacent nodes.

Uploaded by

2104Aishwarya Behere
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
21 views3 pages

HPCPractical 2

The document contains two C++ programs that implement parallel breadth-first search (BFS) and depth-first search (DFS) algorithms using OpenMP for graph traversal. Both programs read a graph's edges, perform the respective search starting from a specified node, and output the visited nodes. The BFS and DFS implementations utilize OpenMP directives to parallelize the processing of adjacent nodes.

Uploaded by

2104Aishwarya Behere
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

1.

Parallel BFS using OpenMP

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

using namespace std;

const int MAXN = 100005;


vector<int> adj[MAXN];
bool visited[MAXN];

void bfs(int start) {


queue<int> q;
[Link](start);
visited[start] = true;

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

// Process node v here

#pragma omp parallel for


for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];

if (!visited[u]) {
visited[u] = true;
[Link](u);
}
}
}
}

int main() {
int n, m, start;
cin >> n >> m >> start;

for (int i = 0; i < m; i++) {


int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

bfs(start);

// Output visited nodes


cout << "Visited nodes: ";
for (int i = 1; i <= n; i++) {
if (visited[i]) {
cout << i << " ";
}
}
cout << endl;

return 0;
}

Output:
671
12
13
24
25
35
46
56
Visited nodes: 1 2 3 4 5 6

2. Parallel dfs using OpenMP

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

using namespace std;

const int MAXN = 100005;


vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int v) {
visited[v] = true;

// Process node v here

#pragma omp parallel for


for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];

if (!visited[u]) {
dfs(u);
}
}
}

int main() {
int n, m, start;
cin >> n >> m >> start;

for (int i = 0; i < m; i++) {


int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

dfs(start);

// Output visited nodes


cout << "Visited nodes: ";
for (int i = 1; i <= n; i++) {
if (visited[i]) {
cout << i << " ";
}
}
cout << endl;

return 0;
}

Output:
671
12
13
24
25
35
46
56
Visited nodes: 1 2 4 6 5 3

You might also like