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-05 [2017/03/19 00:22] mihai.iacov [4.2.1 Implementare] |
laboratoare:laborator-05 [2017/03/19 20:13] florina_elena.barbu [2.2 Structură] |
||
---|---|---|---|
Linia 15: | Linia 15: | ||
====2.2 Structură==== | ====2.2 Structură==== | ||
- | |||
- | #poate o poza si continuare cu exemplu rezolvat# | ||
Un graf are următoarele elemente: | Un graf are următoarele elemente: | ||
Linia 167: | Linia 165: | ||
<file cpp> | <file cpp> | ||
- | Pentru fiecare nod u din graf | + | funcţie |
- | { | + | |
- | | + | |
- | d[u] = infinit | + | |
- | p[u] = null | + | |
- | } | + | |
- | culoare[sursă] = gri; | + | |
- | d[sursă] = 0; | + | |
- | funcţie | + | |
{ | { | ||
pentru fiecare u dintre vecinii nodului curent | pentru fiecare u dintre vecinii nodului curent | ||
Linia 183: | Linia 173: | ||
p[u] = curent | p[u] = curent | ||
d[u] = d[curent] + 1 | d[u] = d[curent] + 1 | ||
- | DFS(u); // | + | pasDFS(u); // |
} | } | ||
culoare[curent] = negru //am terminat explorarea vecinilor nodului curent | 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 | + | Pentru fiecare nod u din graf |
+ | { | ||
+ | | ||
+ | d[u] = infinit | ||
+ | p[u] = null | ||
+ | } | ||
+ | culoare[sursă] = gri; | ||
+ | d[sursă] = 0; | ||
+ | |||
+ | //se apelează iniţial | ||
</ | </ | ||
{{ : | {{ : | ||
+ | |||
+ | ===== 5. Exerciţii ===== | ||
+ | Implementaţi, | ||
+ | - 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 orientat | ||
+ | * 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. | ||
+ | |||
+ | ====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). |