Mentosan

Neorientate - DFS & BFS & Dynamic Allocation

Oct 22nd, 2019
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. int N, M, **mat, **vecini;
  9. bool *verificat;
  10. queue < int > Coada;
  11.  
  12. void DFS(int nod) {
  13.     verificat[nod] = true;
  14.     for(int i = 1; i <= N; i++) {
  15.         int vecin = vecini[nod][i];
  16.         if(vecin != 0 && !verificat[vecin]) {
  17.             cout << vecin << " ";
  18.             DFS(vecin);
  19.         }
  20.     }
  21. }
  22.  
  23. void BFS(int nod) {
  24.     Coada.push(nod);
  25.     verificat[nod] = true;
  26.     while(!Coada.empty()) {
  27.         int vecin = Coada.front();
  28.         Coada.pop();
  29.         for(int i = 1; i <= N; i++) {
  30.             if(mat[vecin][i] == 1 && !verificat[i]) {
  31.                 cout << i << " ";
  32.                 Coada.push(i);
  33.                 verificat[i] = true;
  34.             }
  35.         }
  36.     }
  37. }
  38.  
  39. int main() {
  40.     FILE *in = fopen("graph.in", "r");
  41.     fscanf(in, "%d%d", &N, &M);
  42.     mat = new int*[N + 1];
  43.     vecini = new int*[N + 1];
  44.     for(int i = 1; i <= N; i++) mat[i] = new int[N + 1], vecini[i] = new int[N + 1];
  45.     for(int i = 1; i <= N; i++)
  46.         for(int j = 1; j <= N; j++) mat[i][j] = vecini[i][j] = 0;
  47.  
  48.     while(M--) {
  49.         int x, y;
  50.         fscanf(in, "%d%d", &x, &y);
  51.         mat[x][y] = mat[y][x] = 1;
  52.     }
  53.  
  54.     cout << endl;
  55.     for(int i = 1; i <= N; i++) {
  56.         for(int j = 1; j <= N; j++) cout << mat[i][j] << " ";
  57.         cout << endl;
  58.     }
  59.     cout << endl;
  60.  
  61.     for(int i = 1; i <= N; i++) {
  62.         int k = 1;
  63.         for(int j = 1; j <= N; j++) {
  64.             if(mat[i][j]) {
  65.                 vecini[i][k] = j;
  66.                 k++;
  67.             }
  68.         }
  69.     }
  70.     verificat = new bool[N + 1];
  71.     for(int i = 1; i <= N; i++) verificat[i] = false;
  72.     cout << 1 << " ";
  73.     DFS(1);
  74.     cout << endl;
  75.     for(int i = 1; i <= N; i++) verificat[i] = false;
  76.     cout << 1 << " ";
  77.     BFS(1);
  78.     return 0;
  79. }
RAW Paste Data