Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-05 [2017/03/19 00:22]
mihai.iacov [4.2.1 Implementare]
+++ laboratoare:laborator-05 [2017/03/23 23:03]
iulian.matesica
@@ Linia 15: / Linia 15: @@
 ====2.2 Structură====
-#poate o poza si continuare cu exemplu rezolvat#
 Un graf are următoarele elemente:
@@ Linia 58: / Linia 56: @@
 <note importante>
-Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea
+Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea.
 Se numeşte **lanţ elementar** un lanţ în care nu se repetă vârfuri.
@@ Linia 167: / Linia 166: @@
 <file cpp>
-Pentru fiecare nod u din graf
+funcţie pasDFS(curent)
-{
-     culoare[u]=alb
-     d[u] = infinit    //in d se retine distanta pana la nodul sursa
-     p[u] = null
-}
-culoare[sursă] = gri;
-d[sursă] = 0;
-funcţie DFS(curent)
 {
 	pentru fiecare u dintre vecinii nodului curent
@@ Linia 183: / Linia 174: @@
                p[u] = curent
                d[u] = d[curent] + 1
-               DFS(u);   //adăugăm nodul u în "stivă" şi începem explorarea
+               pasDFS(u);   //adăugăm nodul u în "stivă" şi începem explorarea
           }
 	culoare[curent] = negru   //am terminat explorarea vecinilor nodului curent
+	//ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă
 }
-//se apelează iniţial DFS(sursă)
+Pentru fiecare nod u din graf
+{
+     culoare[u]=alb
+     d[u] = infinit    //in d se retine distanta pana la nodul sursa
+     p[u] = null
+}
+culoare[sursă] = gri;
+d[sursă] = 0;
+//se apelează iniţial pasDFS(sursă)
 </file>
 {{ :laboratoare:df1.jpg |}}
+===== 5. Exerciţii =====
+Implementaţi, pentru fiecare cerinţă, câte o funcţie care:
+  - creează matricea de adiacenţă pentru un graf neorientat cu N noduri, folosindu-se de o listă(sau o matrice cu 2 coloane) de muchii(la alegere - muchiile citite în funcţie sau primite printr-un parametru).
+  - calculează gradul fiecărui nod. Afişaţi numărul de noduri izolate şi numărul de noduri terminale.
+  - primeşte un şir de noduri şi verifică dacă acesta poate reprezenta un lanţ.
+  - primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective
+  - afişează matricea de adiacenţă a unui graf orientat construit astfel:
+    * graful orientat are atâtea arce câte muchii are graful neorientat
+    * există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în graful neorientat.
+    * Extra - câte astfel de grafuri orientate pot fi formate?
+Cerinţele 2, 3, 4 şi 5 se vor folosi de matricea de adiacenţă a grafului de la cerinţa 1.
+====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/lab5_grafuri-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/lab5_grafuri-skel.zip%%''
+  * ''%%unzip lab5_grafuri-skel.zip%%''
+Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
+====De interviu====
+  * Plecând dintr-un nod K, verificaţi dacă puteţi găsi un ciclu în graf.
+  * Verificaţi dacă există un lanţ care uneşte nodurile sursă(S) şi destinaţie(D). Dacă există, cum puteţi găsi lanţul cu număr minim de muchii?
+  * Verificaţi dacă există un lanţ **hamiltonian** în graf.
+  * Verificaţi dacă există un lanţ **eulerian** în graf.
+  * Verificaţi dacă o muchie dată (A, B) este un **pod** pentru drumul de la S la D.
+Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare nod.
+Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie.
+Spunem că muchia (A, B) este pod pentru drumul de la S la D dacă orice lanţ care duce de la S la D trece prin muchia (A, B).

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină