nicuvlad76

Untitled

Jan 27th, 2021
696
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define N 101
  3. using namespace std;
  4. ifstream fin("BFS.in");
  5. ofstream fout("BFS.out");
  6. int n,m,x;
  7. int a[N][N];
  8. void Citire()///citirea datelor
  9. {
  10.    int  i,j;
  11.    fin>>n>>m>>x;
  12.    while(fin>>i>>j)
  13.     a[i][j]=a[j][i]=1;///grafuri neorientate
  14. }
  15. int C[N]; ///coada
  16. bool viz[N]; ///1 daca nod a fost vizitat si 0 altfel
  17. int pr, ul;
  18. int D[N]; ///distanta minima
  19. int T[N];///vectorul de tati
  20. void BFS(int x)///parcurgerea in latime - conexitate , lant minim
  21. {
  22.     ///initializari coada
  23.     pr=ul=1;
  24.     C[pr]=x; ///am introdus pe x in coada
  25.     viz[x]=1;///am vizitat elem din coada
  26.     D[x]=1;
  27.     T[x]=0;
  28.     while(pr<=ul)///mai exista elemente in coada
  29.     {
  30.         int nod=C[pr]; pr++;///extrag primul element
  31.         for(int i=1;i<=n;i++) ///parcurg nodurile
  32.             if(a[nod][i]==1 && viz[i]==0) ///gasesc un vecin nevizitat
  33.             {
  34.                 C[++ul]=i;///am introdus in coada varful i
  35.                 viz[i]=1;///l-am vizitat i
  36.                 D[i]=D[nod]+1;
  37.                 T[i]=nod;///nod este tata lui i
  38.             }
  39.     }
  40. }
  41.  
  42.  void Afisare()
  43.  {
  44.     for(int i=1;i<=ul;i++)
  45.         fout<<C[i]<<' ';
  46.  }
  47.  
  48. int main()
  49. {
  50.     Citire();
  51.     BFS(x);
  52.     Afisare();
  53. }
  54.  
RAW Paste Data