Advertisement
AshfaqFardin

Graph - DFS Algorithm

Aug 24th, 2021
1,043
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5+2; //infinity
  6. bool visited[N] = {false};
  7. vector<int> adj[N];
  8.  
  9. void dfs(int source){
  10.     visited[source] = 1;
  11.     cout << "Node " << source << " is visited"<< endl;
  12.     for(int i = 0; i < adj[source].size(); i++){
  13.         int next = adj[source][i];
  14.         if(visited[next] == 0){
  15.             dfs(next);
  16.         }
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     int numNodes; cin >> numNodes;
  23.     int numEdges; cin >> numEdges;
  24.    
  25.     int edgeA, edgeB;
  26.     for(int i = 0; i < numEdges; i++){
  27.         cin >> edgeA;
  28.         cin >> edgeB;
  29.        
  30.         adj[edgeA].push_back(edgeB);
  31.         adj[edgeB].push_back(edgeA);
  32.     }
  33.    
  34.     dfs(0);
  35.    
  36.    
  37.     return 0;
  38. }
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement