Scribd
Upload
3 views5 pages

Ex 1

The document contains a C++ implementation of a graph class that supports adding edges and performing parallel Breadth-First Search (BFS) and Depth-First Search (DFS). The program prompts the user to input the number of vertices and edges, as well as the edges themselves, before executing the search algorithms starting from a specified vertex. The output displays the order in which vertices are visited during both BFS and DFS.

Uploaded by

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

Ex 1

The document contains a C++ implementation of a graph class that supports adding edges and performing parallel Breadth-First Search (BFS) and Depth-First Search (DFS). The program prompts the user to input the number of vertices and edges, as well as the edges themselves, before executing the search algorithms starting from a specified vertex. The output displays the order in which vertices are visited during both BFS and DFS.

Uploaded by

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

Input

#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>
using namespace std;

class Graph {
int V;
vector<vector<int>> adj;

public:
Graph(int V) {
this->V = V;
[Link](V);
}

void addEdge(int u, int v) {


if (u >= V || v >= V) {
cout << "Invalid edge!" << endl;
return;
}
adj[u].push_back(v);
adj[v].push_back(u);
}

// Parallel BFS
void parallelBFS(int start) {
vector<bool> visited(V, false);
queue<int> q;

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

cout << "Parallel BFS: ";

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

cout << node << " ";

#pragma omp parallel for


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

#pragma omp critical


{
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
}
cout << endl;
}

// SAFE DFS (No parallel recursion)


void parallelDFSUtil(int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";

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


int neighbor = adj[node][i];
if (!visited[neighbor]) {
parallelDFSUtil(neighbor, visited);
}
}
}

void parallelDFS(int start) {


vector<bool> visited(V, false);
cout << "Parallel DFS: ";
parallelDFSUtil(start, visited);
cout << endl;
}
};

int main() {
int V, E;
cout << "Enter number of vertices: ";
cin >> V;

cout << "Enter number of edges: ";


cin >> E;

Graph g(V);
cout << "Enter edges (u v):" << endl;
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
[Link](u, v);
}

int start;
cout << "Enter starting vertex: ";
cin >> start;

[Link](start);
[Link](start);

return 0;
}
Output

Enter number of vertices: 6


Enter number of edges: 7
Enter edges (u v):
01
02
13
14
25
35
45
Enter starting vertex: 0
Parallel BFS: 0 1 2 3 4 5
Parallel DFS: 0 1 3 5 2 4

You might also like