5/25/2018 Algoritmul lui Kruskal

1/12

Proiect realizat de: Capota Alinasi Predescu Iulia

5/25/2018 Algoritmul lui Kruskal

2/12

Descrierea algoritmului

Implementarea algoritmului

Aplicatie practica

Exemplu

Programul in C++

5/25/2018 Algoritmul lui Kruskal

3/12

Algoritmul lui Kruskal,scris de Joseph Kruskal n 1956, este un algoritm n

teoria grafurilor care gsetearborele parialde cost minim pentru un graf

conex ponderat (graf in care fiecare muchie are asociat un cost). Cu alte

cuvinte, gsete submulimea muchiilor care formeaz un arbore careinclude toate vrfurile i care este minimizat din punct de vedere al

costului. Dac graful nu este conex, atunci algoritmul gsete un arbore

parial de cost minim pentru fiecare component conex. Algoritmul lui

Kruskal este un exemplu de algoritm greedy.

5/25/2018 Algoritmul lui Kruskal

4/12

Pentru implementarea algoritmului este necesar rezolvarea urmtoarelor douprobleme:

cum extragem muchia de cost minim

cum testmdacmuchia selectatformeazsau nu cicluri cu cele deja selectate.

Pentru a extrage minimul, o idee ar fi s sortmmuchiile cresctor dupcost i sparcurgem secvenialmuchiile ordonate. Pentru a realiza sortarea muchiilor grafului,vom reprezenta graful prin lista muchiilor (un vector cu m componente, fiecarecomponentfiind o structurn care reinemcele douextremitiicostul muchiei).

O muchie va forma cicluri cu muchiile deja selectate dac i numai dac ntreextremitilemuchiei existcel puinun lan.

Pentru a testa daco muchie formeazcicluri cu muchiile deja selectate este suficientstestmdacextremitilemuchiei se gsescn aceeaicomponentconex. Pentruaceasta va trebui sinempermanent evidenacomponentelor conexe (arborilor) carese formeaz.

5/25/2018 Algoritmul lui Kruskal

5/12

Reprezentarea informaiilor:

n numrulde vrfuri

m numrulde muchii din grafG graful dat, reprezentat prin lista muchiilor (un vector cu mcomponente, fiecare component fiind o structur n carereinemcele douextremitiicostul muchiei)

Aarborele parialde cost minim, reprezentat ca un vector n-1componente n care vom reine indicii din G ai muchiilorselectatec vector cu n componente n care vom reine evidenacomponentelor conexe (c[i] = componenta conex creia iaparinevrful i)

5/25/2018 Algoritmul lui Kruskal

6/12

Trebuie sa conectam 3 orase la o retea telefonica:Bucuresti, Timisoara si Arad.

Necesar cablu: 1300 km.

60

600

640

5/25/2018 Algoritmul lui Kruskal

7/12

E inutil sa executam toate cele trei conexiuni, numai doua din ele suntsuficiente pentru o comunicare in bune conditii intre oricare 2 orase.

De exemplu, legatura Timisoara Arad ar putea lipsi, caz in carenecesarul de cablu devine 1240 km.

640

600

5/25/2018 Algoritmul lui Kruskal

8/12

Sau legatura Timisoara Bucuresti ar putea lipsi,necesarul de cablu devenind 700 km.

60

640

5/25/2018 Algoritmul lui Kruskal

9/12

Oricare 2 legaturi sunt suficiente, deoarece semnalul electric circulasuficient de rapid ca un abonat din Timisoara care doreste sa vorbeasca cuunul din Arad (de exemplu) sa nu-si dea seama ca nu exista legatura

directa intre Timisoara si Arad si ca apelul sau este rutat prin Bucuresti.

Din punctul de vedere al necesarului de cablu, lucrurile nu mai stau la fel.

Conteaza foarte mult care legaturi vor fi realizate si care nu.

Cel mai ieftin ar fi sa alegem legaturile Arad Timisoara si Timisoara Bucuresti si sa evitam legatura Arad - Bucuresti, necesarul de cabluajungand in acest caz la 660 km; aceasta este situatia optima sauacoperirea minimaa retelei.

5/25/2018 Algoritmul lui Kruskal

10/12

Notm cu n numrul de vrfuri din graf (n=|X|). Iniialconsidermcnici o muchie din graf nu a fost selectat,decifiecare vrf din graf este vrf izolat. Cu alte cuvinte, lamomentul iniialavem o pdureformatdin n arbori, fiecarearbore fiind format dintr-un singur vrf. La fiecare pas se

selecteaz o muchie de cost minim care nu a mai fostselectat i care nu formeaz cicluri cu muchiile dejaselectate.

1

1

1

1

1

1

1

1

1

1

1

1

1

1

11

2 3

4

5

11

1

4

32

Exemplu:

5/25/2018 Algoritmul lui Kruskal

11/12

Pasul 1:Selectm o muchie de cost minim. (n cazulnostru, de cost 1).Observai c n graful parial selectatexist n - 1 = 4 arbori, pentru c am unificat arboriicorespunztori extremitilor muchiei selectate. Arboriisunt: { 1, 3 }; { 2 }; { 4 }; { 5 }.

Pasul 2: Selectm din nou o muchie de cost

minim.(Costul minim fiind 1).Observai c n grafulparialselectat existn - 2 = 3 arbori. Arborii sunt:{ 1, 3,4 }; { 2 }; { 5 }.

Pasul 3: La acest pas nu mai putem selecta o muchie de

cost 1, deoarece s-ar obine un ciclu. Selectm muchiade cost 2.Arborii sunt: { 1, 2, 3, 4 }; { 5 }.

Pasul 4: Selectnd, n final, muchia de cost 3, obinemun graf frcicluri cu n-1 muchii, deci un arbore.

5/25/2018 Algoritmul lui Kruskal

12/12

Cod C++:

http://graf.in/