Advertisement
Five_NT

[C++]Algoritmul lui Prim

Mar 20th, 2014
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4.  
  5. ifstream f("date.in");
  6.  
  7. int a[50][50], q[50], h[50], n, r;
  8. const int vmax = 5000;
  9.  
  10. void init_mc()
  11. {
  12.     f>>n;
  13.     for(int i=1; i<=n; i++)
  14.         for(int j=1; j<=n; j++)
  15.             if(i != j)
  16.                 a[i][j] = vmax;
  17. }
  18.  
  19. void citire_mc()
  20. {
  21.     int i, j, c;
  22.     while(f>>i>>j>>c)
  23.     {
  24.         a[i][j] = c;
  25.         a[j][i] = c;
  26.     }
  27. }
  28.  
  29. void init_q()
  30. {
  31.     //int mini = vmax;
  32.     for(int i=1; i<=n; i++)
  33.         if(i != r)
  34.             q[i] = 1;
  35. }
  36.  
  37. int muchie()
  38. {
  39.     int mini = vmax, j;
  40.     for(int i=1; i<=n; i++)
  41.         if(q[i] != 0 && a[q[i]][i] < mini)
  42.         {
  43.             mini = a[q[i]][i];
  44.             j=i;
  45.         }
  46.     return j;
  47. }
  48.  
  49. void ac(int j)
  50. {
  51.     for(int i=1; i<=n; i++)
  52.         if(q[i] != 0 && a[i][q[i]] > a[i][j])
  53.             q[i] = j;
  54. }
  55.  
  56. void afis()
  57. {
  58.     cout<<"APM este format din muchiile: "<<'\n';
  59.     for(int i=1; i<=n; i++)
  60.         if(h[i] != 0)
  61.             cout<<"["<<h[i]<<", "<<i<<"] ";
  62. }
  63.  
  64. int main()
  65. {
  66.     int j, k=0, ct=0;
  67.     init_mc();
  68.     citire_mc();
  69.     cout<<"Nodul initail: "; cin>>r;
  70.     init_q();
  71.     while(k < n-1)
  72.     {
  73.         j = muchie();
  74.         h[j] = q[j];
  75.         ct += a[q[j]][j];
  76.         q[j] = 0;
  77.         ac(j);
  78.         k++;
  79.     }
  80.     cout<<ct<<" "<<endl;
  81.     afis();
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement