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/18 23:35] mihai.iacov [2.2 Structură] |
laboratoare:laborator-05 [2017/03/19 00:30] mihai.iacov [4.2.1 Implementare] |
||
---|---|---|---|
Linia 21: | Linia 21: | ||
* **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului | * **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului | ||
* **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului | * **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului | ||
- | * **Gradul nodului** - Suma muchiilor | + | * **Gradul nodului** - numărul de muchii |
* **Nod izolat** - Un nod ce nu formează nici-o muchie | * **Nod izolat** - Un nod ce nu formează nici-o muchie | ||
* **Noduri terminale** - Un nod ce formează o singură muchie | * **Noduri terminale** - Un nod ce formează o singură muchie | ||
Linia 27: | Linia 27: | ||
* **Nod si muchie incidente** - Nodul face parte dintr-o muchie | * **Nod si muchie incidente** - Nodul face parte dintr-o muchie | ||
+ | <note important> | ||
<note important> | <note important> | ||
\\ | \\ | ||
Linia 75: | Linia 76: | ||
====3.2 Structură==== | ====3.2 Structură==== | ||
- | poza | + | Într-un graf orientat, distingem: |
- | \\ | + | * **gradul interior/ |
+ | * **gradul exterior/ | ||
+ | |||
+ | <note important> | ||
====3.3 Reprezentare==== | ====3.3 Reprezentare==== | ||
Linia 100: | Linia 104: | ||
* nodul sursă (considerat a fi pe nivelul 0) | * nodul sursă (considerat a fi pe nivelul 0) | ||
* vecinii nodului sursă (reprezentând nivelul 1) | * vecinii nodului sursă (reprezentând nivelul 1) | ||
- | * vecinii încă nevizitați ai nodurilot | + | * vecinii încă nevizitați ai nodurilor |
* ș.a.m.d | * ș.a.m.d | ||
Linia 160: | Linia 164: | ||
====4.2.1 Implementare==== | ====4.2.1 Implementare==== | ||
- | <code> | + | Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**, |
- | Cod | + | |
- | </code> | + | <file cpp> |
+ | funcţie pasDFS(curent) | ||
+ | { | ||
+ | pentru fiecare u dintre vecinii nodului curent | ||
+ | dacă culoare[u] == alb | ||
+ | { | ||
+ | | ||
+ | p[u] = curent | ||
+ | d[u] = d[curent] + 1 | ||
+ | | ||
+ | } | ||
+ | culoare[curent] = negru //am terminat explorarea vecinilor nodului curent | ||
+ | //ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă | ||
+ | } | ||
+ | Pentru fiecare nod u din graf | ||
+ | { | ||
+ | | ||
+ | d[u] = infinit | ||
+ | p[u] = null | ||
+ | } | ||
+ | culoare[sursă] = gri; | ||
+ | d[sursă] = 0; | ||
+ | |||
+ | //se apelează iniţial pasDFS(sursă) | ||
+ | |||
+ | </file> | ||
{{ : | {{ : | ||
+ | |||
+ | ===== 5. Exerciţii ===== | ||
+ |