Arbore partial de cost minim

 

Fie urmatoarea problema concreta:

 

Se dau n orase precum si costul conectarii anumitor perechi de orase. Se cere sa se aleaga o parte din muchii astfel incat se asigure existenta unui lant intre oricare doua orase si costul total sa fie minim.

 

G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii). Se cunosc costurile muchiilor. Prin eliminarea unor muchii se obtine un graf partial. Daca acesta este arbore se va numi arbore partial.

 

Costul unui arbore este egal cu suma costurilor muchiilor sale. Arborele partial de cost minim este un arbore pentru care suma este minima.

 

Problema. Fie un graf conex pentru care se cunosc costurile muchiilor. Sa se determine arborele de cost minim asociat (costul arborelui si vectorul de tati).

 

3                                           2

 

5

 

 

4 2 1 7

 

4

 

Vom utiliza 2 vectori :

 

Algoritmul consta in urmatoarele:

Spre exemplu daca v=1 se obtine:

S={0 1 1 1 1}

T={0 0 0 0 0}

 

        Daca distanta de la i la arbore (a[i][s[i]]) este mai mare decat distanta de la i la nodul nod tocmai adaugat la arbore (a[i][nod]) se modifica potentialul ascendent pentru i: s[i]=nod

Pas1

Nod=2

Muchia de cost minim este 1-2 min=2, cost=2

Se obtine :

S={0 0 2 2 1}

T={0 1 0 0 0}

 

 

3        2

 

5

 

 

4 2 1 7

 

4

 

 

Pas2

Nod=4

Muchia de cost minim este (2,4) min=1, cost=3

S={0 0 4 0 1}

T={0 1 0 2 0}

 

 

 

3 2

 

5

 

 

4 2 1 7

 

4

 

 

 

Pas 3

Nod=5

Muchia de cost minim (1,5) min=3 cost=6

S={0,0,4,0,0}

T={0 1 0 2 1}

 

 

 

3        2

 

5

 

 

4 2 1 7

 

4

 

 

 

Pas 4

Nod=3

Muchia de cost minim (4,3), min=4, cost=10

S={0 0 0 0 0}

T={0 1 4 2 1}

 

 

4        2

 

5

 

 

4 2 1 7

 

4

 

 

 

O solutie de implementare:

#include<fstream.h>

#include<values.h>

#include<conio.h>

 

int n,m,v,s[20],t[20];

long int a[20][20],min;

const long int infinit=MAXLONG;

 

void citire()

{int i,j,x,y,z;

fstream f;

f.open("arbminim.txt",ios::in);

if(f)

cout<<"ok"<<endl;

else cout<<"error!!";

 

f>>n>>m;

 

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

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

{if(i==j)

a[i][j]=0;

else

a[i][j]=infinit;

}

 

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

{f>>x>>y>>z;

a[x][y]=a[y][x]=z;}

 

}

 

 

int cauta_nod(int &nod)

{ min=infinit;

for(int i=1;i<=n;i++)

if(s[i]!=0)

if(a[i][s[i]]<min)

{min=a[i][s[i]];

nod=i;}

return min;

}

 

void actualizeaza(int nod)

{for(int i=1;i<=n;i++)

if(s[i])

if(a[i][s[i]]>a[i][nod])

s[i]=nod;

 

}

 

void main()

{ int k,i,j,cost=0;

clrscr();

citire();

cout<<"nodul de inceput ";

cin>>v;

s[v]=0;

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

if(i!=v)

s[i]=v;

 

int nod;

for(k=1;k<=n-1;k++)

{min=cauta_nod(nod);

t[nod]=s[nod];

cost=cost+min;

s[nod]=0;

actualizeaza(nod);

}

 

cout<<"costul este "<<cost<<endl;

cout<<"arborele de cost minimal ";

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

cout<<t[i]<<" ";

getch();

}

 

Probleme propuse

La construirea unui nou oras intr cele n puncte comerciale sunt stabilite initial m drumuri de acces intre perechi de puncte. Pentru fiecare dintre cele m perechi se cunoaste costul constructiei drumului. Dupa o analiza a hartii s-a observat ca unele zone au ramas izolate de altele si specialistii au ajuns la urmatoarea concluzie : sa se elimine o parte din drumurile alese anterior dar sa se adauge drumuri noi de cost z astfel incat sa se obtina o retea noua de drumuri pentru care costul total al constructiei drumurilor sa fie minim si sa existe traseu de acces intre oricare doua puncte comerciale . Sa se afiseze valoarea constructiei si un traseu de la punctul comercial p la punctul 1.

 

Ex :

12

12

1 4 7

4 5 10

5 2 9

2 1 8

3 8 11

8 7 14

7 6 13

3 6 12

9 10 5

10 11 6

11 12 7

9 12 8

 

Z=100

 

Se afiseaza costul 278

Traseul de la 1 la 12 este :

1 8 12