Eternoseeker

Graph DSA

Dec 14th, 2022 (edited)
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | Source Code | 0 0
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. #define size 10
  5.  
  6. class graph{
  7.     int adjacency[size][size]; // adjacency matrix
  8.     int vertices;
  9.     int visited_array[size];
  10. public:
  11.     graph(){
  12.         for(int i = 0; i < size; i++){
  13.             for(int j = 0; j < size; j++){
  14.                 adjacency[i][j] = 0;
  15.             }
  16.         }
  17.         vertices = 0;
  18.         for(int i = 0; i < vertices; i++){
  19.             visited_array[i] = 0;
  20.         }
  21.     }
  22.  
  23.     graph(int v){
  24.         for(int i = 0; i < size; i++){
  25.             for(int j = 0; j < size; j++){
  26.                 adjacency[i][j] = 0;
  27.             }
  28.         }
  29.         vertices = v;
  30.         for(int i = 0; i < size; i++){
  31.             visited_array[i] = 0;
  32.         }
  33.     }
  34.  
  35.     //void create();
  36.  
  37.     void add_edge(int v1, int v2){
  38.         adjacency[v1][v2] = 1;
  39.         adjacency[v2][v1] = 1;
  40.     }
  41.  
  42.     void display(){
  43.         for(int i = 0; i < vertices; i++){
  44.             for(int j = 0; j < vertices; j++){
  45.                 cout << adjacency[i][j] << " ";
  46.             }
  47.             cout << endl;
  48.         }
  49.     }
  50.  
  51.     void bfs(int v){
  52.         queue<int> q;
  53.         int visited[vertices] = {0};
  54.         q.push(v);
  55.         visited[v] = 1;
  56.  
  57.         while(!q.empty()){
  58.             int printVertex = q.front();
  59.             q.pop();
  60.             cout << printVertex << " ";
  61.             for(int i = 0; i < vertices; i++){
  62.                 if(adjacency[printVertex][i] == 1 && (visited[i] == 0)){
  63.                     q.push(i);
  64.                     visited[i] = 1;
  65.                 }
  66.             }
  67.         }
  68.         cout << endl;
  69.  
  70.     }
  71.  
  72.     void dfs(int v){
  73.         int v2 = 0;
  74.         cout << "v: " << v << endl;
  75.         visited_array[v] = 1;
  76.         for(v2 = 0; v2 < vertices; v2++){
  77.             if((adjacency[v][v2] == 1)){
  78.                 if(visited_array[v2] == 0){
  79.                     dfs(v2);
  80.                 }
  81.             }
  82.         }
  83.     }
  84.  
  85. };
  86.  
  87. int main(){
  88.     graph g(6);
  89.     g.add_edge(1, 2);
  90.     g.add_edge(5, 2);
  91.     g.add_edge(1, 0);
  92.     g.add_edge(2, 3);
  93.     g.add_edge(3, 4);
  94.     g.bfs(1);
  95.     g.dfs(1);
  96.     g.display();
  97.     return 0;
  98. };
  99.  
Add Comment
Please, Sign In to add comment