GRAFURI PONDERATE

Problema:

Algoritmul Krustal pentru determinarea arborelui partial de cost minim

Fisierul "graf.txt"

6 // reprezinta numarul de noduri

1 2 3 4 5 6 //acestea sunt nodurile

9 //reprezinta numarul de muchii existente in graf, inseamna ca avem 9 linii in continuare

1 2 1 // exista muchie intre 1 si 2, iar costul acesteia este 1

1 3 4 // exista muchie intre 1 si 3, iar costul acesteia este 4

1 4 10

2 5 3

2 6 2

3 5 1

4 5 20

4 6 30

5 6 1

Astfel, facem o matrice cu "numarMuchii" linii si 3 coloane.

Cod:

#include <iostream>

#include <fstream>

#define MAX 100

#define numarColoane 3

using namespace std;

int numarNoduri;

int numarLinii;

int matriceAdiacenta[MAX][MAX];

int vector[MAX];

void citire()

{

ifstream f("graf.txt");

int i,j;

f>>numarNoduri;

for(i=1;i<=numarNoduri;i++)

f>>vector[i];

f>>numarLinii;

for(i=1;i<=numarLinii;i++)

for(j=1;j<=numarColoane;j++)

f>>matriceAdiacenta[i][j];

f.close();

}

void sortare()

{

int i,j,s=0,aux;

do{ s=0;

for(i=1;i<=numarLinii-1;i++)

if(matriceAdiacenta[i][numarColoane]>matriceAdiacenta[i+1][numarColoane])

{

for(j=1;j<=numarColoane;j++)

{

aux=matriceAdiacenta[i][j];

matriceAdiacenta[i][j]=matriceAdiacenta[i+1][j];

matriceAdiacenta[i+1][j]=aux;

s=1;

}

}

}while(s!=0);

}

void afisareMatrice()

{

int i,j;

for(i=1;i<=numarLinii;i++)

{

for(j=1;j<=numarColoane;j++)

cout<<matriceAdiacenta[i][j]<<" ";

cout<<endl;

}

}

void kruskal()

{

int cost=0,numarLegaturi=0,liniaCurenta=1,aux,i;

cout<<"Legaturile:"<<endl;

while(numarLegaturi<numarNoduri-1)

{

int nodPlecare=matriceAdiacenta[liniaCurenta][1];

int nodDestinatie=matriceAdiacenta[liniaCurenta][2];

if(vector[nodPlecare]!=vector[nodDestinatie])

{

cost=cost+matriceAdiacenta[liniaCurenta][numarColoane];

numarLegaturi++;

cout<<"("<<nodPlecare<<","<<nodDestinatie<<")";

aux=vector[nodDestinatie];

for(i=1;i<=numarNoduri;i++)

if (vector[i]==aux)

vector[i]=vector[nodPlecare];

}

liniaCurenta++;

}

cout<<endl<<"Cost: "<<cost<<endl;

}

int main()

{

cout << "Hello world!" << endl;

citire();

afisareMatrice();

sortare();

cout<<endl;

afisareMatrice();

kruskal();

return 0;

}