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 Ultima versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-06 [2017/03/23 13:39] florina_elena.barbu [4. Algoritmul lui Prim] |
laboratoare:laborator-06 [2017/03/30 22:27] iulian.matesica |
||
---|---|---|---|
Linia 67: | Linia 67: | ||
{{ : | {{ : | ||
+ | |||
+ | |||
+ | {{ : | ||
===== 4. Algoritmul lui Prim ===== | ===== 4. Algoritmul lui Prim ===== | ||
Linia 84: | Linia 87: | ||
{{ : | {{ : | ||
- | <file cpp> | ||
- | PRIM(G, w, r) | ||
- | 1 Q V[G] | ||
- | |||
- | 2 for each u Q | ||
- | |||
- | 3 do key[u] | ||
- | |||
- | 4 key [r] 0 | ||
- | |||
- | 5 [r] NIL | ||
- | |||
- | 6 while Q | ||
- | |||
- | 7 do u EXTRACT-MIN(Q) | ||
- | |||
- | 8 for each v Adj[u] | ||
- | |||
- | 9 do if v Q and w (u, v) < key[v] | ||
- | |||
- | 10 then [v] u | ||
- | |||
- | 11 | ||
- | </ | ||
{{ : | {{ : | ||
===== 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 | + | 1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora |
<file cpp> | <file cpp> | ||
Linia 134: | Linia 113: | ||
7 8 2 | 7 8 2 | ||
</ | </ | ||
+ | |||
+ | ====5.1. Exerciții - schelet de laborator==== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | |||
+ | ==== Extra ==== | ||
+ | - Se dă un graf care coincide cu un arbore minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ce va fi scoasă. | ||
+ | - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din graf. Care este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V). | ||
+ | - Se dă un graf care coincide cu un arbore minim de acoperire şi un nod auxiliar care formează doar două muchii. Verificaţi dacă folosirea nodului auxiliar pentru a conecta nodurile duce la un arbore de acoperire cu un cost mai mic. | ||
+ | |||
+ | |||
===== 6. Referințe ===== | ===== 6. Referințe ===== | ||
- [[https:// | - [[https:// |