Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Arbore partial de cost minim

No description
by

Anca Hoitan

on 21 February 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Arbore partial de cost minim

Arbore parțial de cost minim
Principiul de functionare al algoritmului
Program C++
Algoritmul lui Kruskal
Este un algoritm de determinare a arborelui parțial de cost minim. Se poate aplica doar pe vector de muchii.
Se porneste de la principiul că fiecare nod reprezintă inițial un arbore. Se ordonează muchiile în ordine crescătoare după costul fiecărei muchii.
Apoi, se parcurge vectorul de muchii începând cu prima pozitie și se adaugă câte o muchie astfel încât să nu se formeze cicluri, iar costul să fie minim.
Marcăm nodurile care formează arborele cu ultimul nod adăugat astfel încât în final toate vor fi marcate la fel.
Pasul 1
Pasul 2
Citirea din fişierul "graf.txt"
Pasul 3
Ordonarea vectorului de muchii după cost
Pasul 4
Crearea și afișarea arborelui parțial de cost minim
Date de ieşire
1 3
2 5
4 5
4 6
1 4
12

Concluzii
Algoritmul lui Kruskal are complexitatea O(m^2), unde m reprezintă numărul de muchii. Astfel, dacă numărul de muchii este mic, se preferă folosirea algoritmului lui Kruskal.
Algoritmul lui Kruskal
Exemplu
Fie graful ponderat:
1
2
3
4
5
6
6
5
5
6
2
5
4
3
1
5
2
2
2
1
2
3
4
5
6
Variabilele utilizate în program
int n, m, a[20]; /* n - numărul de noduri
m - numărul de muchii
a - vectorul de arbori */
muchie v[50]; // vectorul de muchii
int ct; // costul minim final
int k; // numărătorul
void citire(){
ifstream f("graf.txt");
f>>n>>m;
int i;
for(i=1; i<=m; i++) f>>v[i].e1>>v[i].e2>>v[i].c;
f.close();
}
void ordonare(){
int i, j;
muchie aux;
for(i=1; i<m; i++)
for(j=i+1; j<=m; j++)
if(v[i].c > v[j].c){
aux=v[i]; v[i]=v[j]; v[j]=aux;
}
}
int main(){
citire();
ordonare();
int i, j, k=0, ct=0;
for(i=1; i<=n; i++) a[i]=i;
i=1;
ofstream g("apm.txt");
while(k < n-1) {
if(a[v[i].e1]!=a[v[i].e2]){
k++;
ct=ct+v[i].c;
for(j=1; j<=n; j++)
if(a[j]==a[v[i].e1])
a[j]=a[v[i].e2];
g<<v[i].e1<<" "<<v[i].e2<<endl;
}
i++;
}
g<<ct<<endl;
g.close();
return 0;
}

Date de intrare
"graf.txt"
6 11
1 2 6
1 3 1
1 4 5
2 3 5
2 5 2
3 4 5
3 5 6
3 6 5
4 5 2
4 6 2
5 6 4
"apm.txt"
Full transcript