Algoritmul lui Kruskal

Trimis la data: 2016-01-20 Materia: Informatica Nivel: Facultate Pagini: n/a Nota: / 10 Downloads: 0
Autor: Filimon Nadia Dimensiune: 221kb Voturi: Tipul fisierelor: odp Acorda si tu o nota acestui referat: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
Algoritmul lui Kruskal, scris de Joseph Kruskal in 1956, este un algoritm in teoria grafurilor care gaseste arborele partial de cost minim pentru un graf conex ponderat (graf in care fiecare muchie are asociat un cost). Cu alte cuvinte, gaseste submultimea muchiilor care formeaza un arbore care include toate varfurile si care este minimizat din punct de vedere al costului. Daca graful nu este conex, atunci algoritmul gaseste un arbore partial de cost minim pentru fiecare componenta conexa. Algoritmul lui Kruskal este un exemplu de algoritm greedy.

- numarul de varfuri
m - numarul de muchii din graf
G - graful dat, reprezentat prin lista muchiilor (un vector cu m componente, fiecare componenta fiind o structura in care retinem cele doua extremitati si costul muchiei)
A - arborele partial de cost minim, reprezentat ca un vector n-1 componente in care vom retine indicii din G ai muchiilor selectate
c - vector cu n componente in care vom retine evidenta componentelor conexe (c[i] = componenta conexa careia ii apartine varful i)

Oricare 2 legaturi sunt suficiente, deoarece semnalul electric circula suficient de rapid ca un abonat din Timisoara care doreste sa vorbeasca cu unul 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 cablu ajungand in acest caz la 660 km; aceasta este situatia optima - sau "acoperirea minima" a retelei. Notam cu n numarul de varfuri din graf (n=|X|). Initial consideram ca nici o muchie din graf nu a fost selectata, deci fiecare varf din graf este varf izolat. Cu alte cuvinte, la momentul initial avem o padure formata din n arbori, fiecare arbore fiind format dintr-un singur varf. La fiecare pas se selecteaza o muchie de cost minim care nu a mai fost selectata si care nu formeaza cicluri cu muchiile dejaselectate.

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Filmele zilei
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10 Bacalaureat 2017 Vezi subiectele examenului de Bacalaureat din 2017 Evaluare Nationala 2017 Ultimele informatii despre evaluare nationala
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.
Acest site foloseste cookies: Prin navigarea pe acest site, va exprimati acordul asupra folosirii cookie-urilor. Detalii aici OK