Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <omp.h>
- #include <bits/stdc++.h>
- using namespace std;
- void dfs(int start, int* arr, int n, int visited[]) {
- #pragma omp parallel for ordered
- for(int i = 0; i < n; i++) {
- #pragma omp ordered
- if( (*(arr + (start*n) + i) == 1) && (!visited[i]) )
- {
- visited[i] = 1;
- cout<<i<<" ";
- dfs(i, (int*)arr, n, visited);
- }
- }
- }
- int main()
- {
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- 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 visited[n] = {0};
- cout<<"Enter the start vertex: ";
- int start;
- cin>>start;
- clock_t strt = clock();
- cout<<start<<" ";
- visited[start] = 1;
- dfs(start, (int *)arr, n, visited);
- clock_t stop = clock();
- cout<<"\nTime required : "<<(double)(stop-strt)<<" ms"<<endl;
- return 0;
- }
- /*
- "Parallel Execution"
- PS D:\C++> g++ -fopenmp parallel_dfs.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 3 4 2 5 6
- Time required : 9 ms
- "Serial Execution"
- PS D:\C++> g++ parallel_dfs.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 3 4 2 5 6
- Time required : 12 ms
- */
- /*
- This code implements Depth-First Search (DFS) for a graph represented as an adjacency matrix. Let's break it down:
- 1. **`dfs` Function:**
- - This function performs a Depth-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 marks it as visited, prints the vertex, and recursively calls `dfs` with it as the starting vertex.
- 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.
- - DFS traversal is initiated from a user-defined starting vertex.
- - The time taken for the DFS traversal is measured using the `clock` function.
- 3. **OpenMP Parallelization:**
- - OpenMP directives (`#pragma omp parallel for ordered`) are used to parallelize the loop iterations.
- - The `ordered` pragma ensures that the traversal order is maintained while still allowing parallel execution.
- 4. **Output:**
- - The DFS traversal sequence starting from the specified vertex is printed.
- - The time taken for the DFS traversal is also printed in milliseconds.
- 5. **Performance Comparison:**
- - The code demonstrates the difference in execution time between parallel and serial DFS traversal.
- - Parallel execution is expected to be faster than serial execution due to concurrent processing of vertices.
- 6. **Sample Output:**
- - For the given input graph with vertices `{0, 1, 2, 3, 4, 5, 6}` and edges `{(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)}`,
- starting from vertex 0, the DFS traversal sequence is `{0, 1, 3, 4, 2, 5, 6}`.
- - The time required for parallel execution is 9 milliseconds, while for serial execution, it is 12 milliseconds.
- Overall, this code showcases how Depth-First Search can be implemented for graph traversal using OpenMP parallelization,
- potentially improving performance by leveraging multiple threads to process vertices concurrently.
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement