Arbori-Determinare arbore 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.

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;

}