Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-06 [2017/03/23 13:17]
florina_elena.barbu [3. Algoritmul lui Kruskal]
+++ laboratoare:laborator-06 [2017/03/23 21:28]
mihai.iacov [3. Algoritmul lui Kruskal]
@@ Linia 67: / Linia 67: @@
 {{ :laboratoare:kruskal.gif?900 |}}
+{{ :laboratoare:kruskal2.gif?900 |}}
 ===== 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: Vnou = {x}, unde x este un nod arbitrar (punct de plecare) din V, Enou= {} repetă până când Vnou=V:
+        * 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
+</note>
+{{ :laboratoare:prim.gif?900 |}}
+{{ :laboratoare:prim2.gif?900 |}}
 ===== 5. Exerciții de laborator =====
+.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
+13
+2 4
+3 9
+4 1
+6 7
+3 12
+4 4
+8 13
+5 7
+6 8
+6 3
+7 6
+8 5
+8 2
+</file>
 ===== 6. Referințe =====
   - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]]

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină