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 13:00] florina_elena.barbu |
laboratoare:laborator-05 [2017/03/19 00:30] mihai.iacov [4.2.1 Implementare] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator | + | ====== Laborator |
\\ | \\ | ||
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 | ||
* **Noduri adiacente** - Noduri intre care există o muchie | * **Noduri adiacente** - Noduri intre care există o muchie | ||
* **Nod si muchie incidente** - Nodul face parte dintr-o muchie | * **Nod si muchie incidente** - Nodul face parte dintr-o muchie | ||
+ | |||
+ | <note important> | ||
+ | <note important> | ||
\\ | \\ | ||
\\ | \\ | ||
Linia 56: | Linia 59: | ||
<note importante> | <note importante> | ||
Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1, | Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1, | ||
+ | |||
+ | Se numeşte **lanţ elementar** un lanţ în care nu se repetă vârfuri. | ||
+ | |||
+ | Se numeşte **lanţ simplu** un lanţ în care nu se repetă muchii. | ||
+ | |||
+ | Se numeşte **ciclu** un lanţ simplu pentru care primul şi ultimul vârf coincid. | ||
+ | |||
+ | Se numeşte **ciclu elementar** un ciclu în care nu se repetă vârfuri(excepţie primul şi ultimul). | ||
</ | </ | ||
Linia 65: | 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 90: | 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 150: | 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 ===== | ||
+ |