nicuvlad76

Untitled

Jan 27th, 2021
743
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 Init()
  21. {
  22.     pr=ul=1;
  23.     C[pr]=x; ///am introdus pe x in coada
  24.     viz[x]=1;///am vizitat elem din coada
  25.     D[x]=1;
  26.     T[x]=0;
  27. }
  28. void BFS(int x)///parcurgerea in latime - conexitate , lant minim
  29. {
  30.     ///initializari coada
  31.  
  32.     if(pr<=ul)///mai exista elemente in coada
  33.     {
  34.         int nod=C[pr]; pr++;///extrag primul element
  35.         for(int i=1;i<=n;i++) ///parcurg nodurile
  36.             if(a[nod][i]==1 && viz[i]==0) ///gasesc un vecin nevizitat
  37.             {
  38.                 C[++ul]=i;///am introdus in coada varful i
  39.                 viz[i]=1;///l-am vizitat i
  40.                 D[i]=D[nod]+1;
  41.                 T[i]=nod;///nod este tata lui i
  42.             }
  43.         BFS(nod);
  44.     }
  45. }
  46.  
  47.  void Afisare()
  48.  {
  49.     for(int i=1;i<=ul;i++)
  50.         fout<<C[i]<<' ';
  51.  }
  52.  
  53. int main()
  54. {
  55.     Citire();
  56.     Init();
  57.     BFS(x);
  58.     Afisare();
  59. }
  60.  
RAW Paste Data