Unelte utilizator
laboratoare:laborator-06
Diferențe
Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
| Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
|
laboratoare:laborator-06 [2017/03/21 02:18] mihai.iacov [2.3 Arbore vs. pădure de acoperire] |
laboratoare:laborator-06 [2017/03/23 21:28] mihai.iacov [3. Algoritmul lui Kruskal] |
||
|---|---|---|---|
| Linia 48: | Linia 48: | ||
| ===== 3. Algoritmul lui Kruskal ===== | ===== 3. Algoritmul lui Kruskal ===== | ||
| + | Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. | ||
| + | |||
| + | Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. | ||
| + | |||
| + | Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de **algoritm greedy**. | ||
| + | |||
| + | <note tip> | ||
| + | Algoritmul funcționează în felul următor: | ||
| + | |||
| + | * creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat | ||
| + | * creează o mulțime S care conține toate muchiile din graf | ||
| + | * atât timp cât S este nevidă | ||
| + | * elimină o muchie de cost minim din S | ||
| + | * dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur | ||
| + | * altfel, ignoră muchia | ||
| + | |||
| + | </ | ||
| + | |||
| + | {{ : | ||
| + | |||
| + | |||
| + | {{ : | ||
| ===== 4. Algoritmul lui Prim ===== | ===== 4. Algoritmul lui Prim ===== | ||
| + | Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat. | ||
| + | |||
| + | <note tip> | ||
| + | Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile. | ||
| + | |||
| + | * Intrare: Un graf conex ponderat cu nodurile V și muchiile E. | ||
| + | * Initializare: | ||
| + | * Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar) | ||
| + | * Se adaugă v la Vnou, (u,v) la Enou | ||
| + | * Ieșire: Vnou și Enou descriu arborele parțial de cost minim | ||
| + | |||
| + | </ | ||
| + | |||
| + | {{ : | ||
| + | |||
| + | |||
| + | |||
| + | {{ : | ||
| ===== 5. Exerciții de laborator ===== | ===== 5. Exerciții de laborator ===== | ||
| + | 1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei carora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigure conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale. | ||
| + | <file cpp> | ||
| + | # explicatii format | ||
| + | # n=numar varfuri m=numar muchii | ||
| + | # m randuri, cate unul pentru fiecare muchie: start end cost | ||
| + | 8 13 | ||
| + | 1 2 4 | ||
| + | 1 3 9 | ||
| + | 1 4 1 | ||
| + | 1 6 7 | ||
| + | 2 3 12 | ||
| + | 2 4 4 | ||
| + | 3 8 13 | ||
| + | 4 5 7 | ||
| + | 4 6 8 | ||
| + | 5 6 3 | ||
| + | 5 7 6 | ||
| + | 5 8 5 | ||
| + | 7 8 2 | ||
| + | </ | ||
| ===== 6. Referințe ===== | ===== 6. Referințe ===== | ||
| - [[https:// | - [[https:// | ||
laboratoare/laborator-06.txt · Ultima modificare: 2018/02/25 22:43 de către mihai.iacov
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
