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:42]
florina_elena.barbu [4. Algoritmul lui Prim]
+++ laboratoare:laborator-06 [2017/03/30 22:27]
iulian.matesica
@@ Linia 68: / Linia 68: @@
 {{ :laboratoare:kruskal.gif?900 |}}
-<file cpp>
-KRUSKAL(G, w)
-  A
-  for each vertex v  V[G]
-      do MAKE-SET (v)
-  sort the edges of E by nondecreasing weight w
-  for each edge (u, v)  E, in order by nondecreasing weight
-      do if FIND-SET(u)  FIND-SET(v)
-            then A  A  {(u, v)}
-                 UNION (u, v)
-  return A
-</file>
 {{ :laboratoare:kruskal2.gif?900 |}}
@@ Linia 108: / Linia 87: @@
 {{ :laboratoare:prim.gif?900 |}}
-<file cpp>
-PRIM(G, w, r)
-</file>
 {{ :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.
+.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale.
 <file cpp>
@@ Linia 138: / Linia 113: @@
 8 2
 </file>
+====5.1. Exerciții - schelet de laborator====
+Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+=== Linux===
+Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip%%''
+  * ''%%unzip lab6_arbori_min-skel.zip%%''
+Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
+==== 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 =====
   - [[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ă