Determinarea arborelui partial de cost minim

Enunt

Se dă un graf neorientat G=(U,X), conex, ponderat cu N noduri. Se cere sa se arborele partial de cost minim asociat grafului dat.

Datele de intrare se vor citi din fisierul text graf.in, care conţine pe prima linie două numere naturale n (numărul de noduri) şi m (numărul de muchii), iar pe următoarele m linii triplete de numere naturale x, y, cost, care reprezintă muchia (x,y) şi costul asociat acesteia.
Datele de iesire vor fi afişate pe ecran în următorul format:
  • muchiile care formează arborele parţial de cost minim
  • costul arborelui partial determinat rezultatul va fi afisat pe ecran.
 graf.in  Rezultat
9 11
3 8 1
2 3 2
1 2 1
1 3 2
1 4 1
4 5 2
5 6 3
3 6 1
3 9 2
8 9 3
7 8 3
 Arborele parţial de cost minim conţine muchiile:
(3,8), (1,2), (1,4), (3,6), (6,9), (2,3), (4,5), (7,8)
Costul APCM:12
Indicaţii de rezolvare:
    Există situaţii în care se poate asocia o valoare suplimentară unei muchii, valoare care reprezintă distanţa dintre noduri, costul asociat muchiei, timpul de parcurs al muchiei, etc. Această nouă caracteristică se mai numeşte si pondere.
    Pentru a memora un graf ponderat în memoria calculatorului se pot utiliza mai multe variante :
  • matricea de adiacenţă: care in dreptul  muchiei (x,y) va memora valoarea costului muchiei
  • matricea costurilor: este o matrice care are un număr de linii egal cu numărul de muchii şi trei coloane care memorează muchia (x,y) şi costul acesteia.

Definiţie: Costul grafului este suma ponderilor tuturor muchiilor din graf.

Definiţie: A

Program Code Bloks:

//Algoritmul lui KRUSKAL
#include<iostream>
#include<fstream>
using namespace std;
int a[50][4],n,m; //n-nr. de noduri, m-nr. de muchii
//citirea din fisier a informatiilo si construirea matricei costurilor
void citire(int a[50][4], int &n, int &m)
{ ifstream f(“matrice.in”);
  f>>n>>m;
  for(int i=1;i<=m;i++)
f>>a[i][1]>>a[i][2]>>a[i][3];
  f.close();
}
//afisarea pe ecran
void afisare(int a[50][4], int m)
{cout<<“Maticea costurilor este:”<<endl;
for(int i=1;i<=m;i++)
{ for(int j=1;j<=3;j++)
cout<<a[i][j]<<” “;
              cout<<endl;
                }
}
//ordonarea matricei costurilor dupa ultima coloana
void ordoneaza(int a[50][4], int m)
{//Buble – sort
int ok;//presupun matricea ordonata dupa ultima coloana
do
        {ok=1;
        for(int i=1;i<=m-1;i++)
if(a[i][3]>a[i+1][3])
{ //se inverseaza linia i cu linia i+1
for(int j=1;j<=3;j++)
{int aux=a[i][j];
a[i][j]=a[i+1][j];
a[i+1][j]=aux;
                          ok=0;
                         }
         }while(ok==0);
        }
void kruskal(int a[50][4],int m,int n)
{ //construim un vector v cu un numar de elemente egal cu numarul de noduri,
 //   v[i]->componenta conexa a nodului i
 int v[20],cost=0,nr_muchii=0,k;
 for(int i=1;i<=n;i++)
    v[i]=i;                        //fiecare nod formeaza o componenta conexa
 k=1;//numarul liniei care se prelucreaza dim matrice
 cout<<“APCM contine urmatoarele muchii:”<<endl;
 while(nr_muchii<n-1)
    {
        //linia k se adauga sau nu la APCM?
        int x=a[k][1];
        int y=a[k][2];
        if(v[x]!=v[y])//x si y fac parte din componente conexe diferite
          {
              cost=cost+a[k][3];
              nr_muchii++;
              cout<<“(“<<x<<“,”<<y<<“)”;
              int aux=v[y];
              for(int i=1;i<=n;i++)
                if (v[i]==aux)
                  v[i]=v[x];
          }
        k++;
    }
    cout<<“Costul APCM este “<<cost<<endl;
}
int main()
{ citire(a,n,m);
  cout<<“Initial:”<<endl;
  afisare(a,m);
  ordoneaza(a,m);
  cout<<“Dupa ordonare crescatoare a coloanei 3:”<<endl;
  afisare(a,m);
  kruskal(a, m, n);
  return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s