Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<omp.h>
- #include<queue>
- #include<bits/stdc++.h>
- using namespace std;
- queue<int>q;
- void bfs(int start, int* arr, int n, int visit[])
- {
- #pragma omp parallel for ordered
- for(int i=0; i<n; i++)
- {
- #pragma omp ordered
- if( ( *(arr + (n*start) + i) == 1 ) && (visit[i] == 0) )
- {
- cout<<i<<" ";
- q.push(i);
- visit[i] = 1;
- }
- }
- q.pop();
- if(!q.empty()) bfs(q.front(), (int*)arr, n, visit);
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- //cout<<"BFS 0 1 2 3 4 5 6"<<endl;
- cout<<"Enter the number of vertices: ";
- int n;
- cin>>n;
- int arr[n][n] = {0};
- cout<<"Enter the number of edges: ";
- int edges;
- cin>>edges;
- for(int j=0; j<edges; j++)
- {
- int a, b;
- cout<<"Enter the two edges:"<<endl;
- cin>>a>>b;
- arr[a][b] = 1;
- arr[b][a] = 1;
- }
- int visit[n] = {0};
- cout<<"Enter the start vertex: ";
- int start;
- cin>>start;
- clock_t strt = clock();
- visit[start] = 1;
- cout<<start<<" ";
- q.push(start);
- bfs(start, (int*)arr, n, visit);
- clock_t stop = clock();
- cout<<"\nTime required : "<<(double)(stop-strt)<<" ms"<<endl;
- return 0;
- }
- /*
- "Parallel Execution"
- PS D:\C++> g++ -fopenmp parallel_bfs.cpp
- PS D:\C++> ./a out
- Enter the number of vertices: 7
- Enter the number of edges: 6
- Enter the two edges:
- 0 1
- Enter the two edges:
- 0 2
- Enter the two edges:
- 1 3
- Enter the two edges:
- 1 4
- Enter the two edges:
- 2 5
- Enter the two edges:
- 2 6
- Enter the start vertex: 0
- 0 1 2 3 4 5 6
- Time required : 3 ms
- "Serial Execution"
- PS D:\C++> g++ parallel_bfs.cpp
- PS D:\C++> ./a out
- Enter the number of vertices: 7
- Enter the number of edges: 6
- Enter the two edges:
- 0 1
- Enter the two edges:
- 0 2
- Enter the two edges:
- 1 3
- Enter the two edges:
- 1 4
- Enter the two edges:
- 2 5
- Enter the two edges:
- 2 6
- Enter the start vertex: 0
- 0 1 2 3 4 5 6
- Time required : 11 ms
- */
- /*
- This code implements a Breadth-First Search (BFS) algorithm for a graph represented as an adjacency matrix. Let's analyze it:
- 1. **`bfs` Function:**
- - The function `bfs` performs a Breadth-First Search traversal starting from a given vertex.
- - It iterates over the vertices adjacent to the `start` vertex in parallel using OpenMP directives.
- - Each thread checks if an adjacent vertex is reachable from the `start` vertex and if it has been
- visited before. If not visited, it prints the vertex, marks it as visited, and enqueues it.
- - The traversal continues by dequeuing the next vertex from the queue and recursively calling `bfs`
- until the queue is empty.
- 2. **`main` Function:**
- - It initializes the graph as an adjacency matrix `arr`, where `arr[i][j]` is 1 if there is an edge
- between vertices `i` and `j`.
- - User input is taken for the number of vertices `n`, the number of edges `edges`, and the edges themselves.
- - BFS traversal is initiated from a user-defined starting vertex.
- - The time taken for the BFS traversal is measured using the `clock` function.
- 3. **Parallel Execution:**
- - OpenMP directives (`#pragma omp parallel for ordered`) are used to parallelize the loop that iterates
- over adjacent vertices.
- - The `ordered` pragma ensures that the traversal order is maintained while still allowing parallel execution.
- 4. **Output:**
- - The BFS traversal sequence starting from the specified vertex is printed.
- - The time taken for the BFS traversal is also printed in milliseconds.
- 5. **Performance Consideration:**
- - Parallelizing BFS traversal can improve performance by utilizing multiple threads to explore adjacent
- vertices concurrently.
- - However, the efficiency of parallelization depends on factors such as the number of vertices, edges, and
- the distribution of edges in the graph.
- 6. **Time Complexity:**
- - The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges.
- - In this implementation, parallelization aims to improve performance but does not change the time complexity
- of the BFS algorithm.
- Overall, this code demonstrates how Breadth-First Search can be implemented for graph traversal using OpenMP to
- potentially improve performance through parallel execution.
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement