Algoritmul lui Kruskal

5x puncte

categorie: Informatica

nota: 9.89

nivel: Facultate

- 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 [...]
DOWNLOAD REFERAT

Preview referat: Algoritmul lui Kruskal

- 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.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.