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/05 13:22] florina_elena.barbu [5. Referințe] |
laboratoare:laborator-05 [2017/03/19 00:27] mihai.iacov [4.2.1 Implementare] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 05: Arbori minimi de acoperire | + | ====== Laborator 05: Introducere în teoria grafurilor |
- | ===== 1. Obiective laborator===== | + | \\ |
- | * Înțelegerea conceptului de arbore minim de acoperire | + | =====1 |
- | * Înțelegerea implementării algoritmilor care determină acest arbore | + | *Definirea structurii și elementelor unui graf neorientat |
- | * Înțelegere aplicațiilor practice în: | + | *Definirea structurii și elementelor |
- | * rețele de calculatoare: | + | |
- | * prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală) | + | |
- | * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, | + | |
- | ===== 2. Algoritmul lui Kruskal ===== | ||
- | ===== 3. Algoritmul lui Prim ===== | ||
- | ===== 4. Exerciții de laborator ===== | + | =====2 Grafuri neorientate===== |
+ | ====2.1 Definiție==== | ||
+ | Un **graf neorientat** este o pereche ordonată de multimi(X, | ||
+ | *X este o mulțime finită și nevidă de elemente numite **noduri** sau **vârfuri** | ||
+ | *U este o mulțime de perechi neordonate din X,numite **muchii** | ||
+ | ====2.2 Structură==== | ||
- | ===== 5. Referințe ===== | + | #poate o poza si continuare cu exemplu rezolvat# |
- | - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]] | + | |
- | - [[https://en.wikipedia.org/ | + | Un graf are următoarele elemente: |
- | | + | * **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului |
- | | + | * **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului |
- | | + | * **Gradul nodului** - numărul de muchii formate cu ajutorul nodului respectiv |
+ | * **Nod izolat** - Un nod ce nu formează nici-o muchie | ||
+ | * **Noduri terminale** - Un nod ce formează o singură muchie | ||
+ | * **Noduri adiacente** - Noduri intre care există o muchie | ||
+ | * **Nod si muchie incidente** - Nodul face parte dintr-o muchie | ||
+ | |||
+ | <note important> | ||
+ | <note important> | ||
+ | \\ | ||
+ | \\ | ||
+ | |||
+ | ====2.3 Reprezentare | ||
+ | * **Matricea de adiacență** | ||
+ | *a[i,j] = 1 ,dacă ∃ muchia [i,j] cu i≠j | ||
+ | | ||
+ | * **Lista de adiacență** - este un tablou de liste egal cu numarul de varfuri; | ||
+ | * **Vectorul de muchii** - mulțime ce conține toate muchiile grafului | ||
+ | |||
+ | {{ :laboratoare: | ||
+ | |||
+ | Având lista de adiacentă: | ||
+ | * **A**: | ||
+ | * **B**: | ||
+ | * **C**: | ||
+ | * **D**: | ||
+ | * **E**: | ||
+ | |||
+ | <note importante> | ||
+ | Un **graf parțial** este un graf obținut din graful inițial prin eliminarea uneia sau mai multor muchii | ||
+ | </note> | ||
+ | |||
+ | |||
+ | <note importante> | ||
+ | Un **subgraf** este un graf obținut din graful inițial prin eliminarea unui număr de noduri impreună cu muchiile formate cu acele noduri | ||
+ | </note> | ||
+ | |||
+ | <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, | ||
+ | |||
+ | 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). | ||
+ | </note> | ||
+ | |||
+ | =====3 Grafuri orientate===== | ||
+ | ====3.1 Definiție==== | ||
+ | Un **graf orientat** este o pereche ordonată de mulțimi G={X, | ||
+ | *X este o mulțime finită și nevidă numită mulțimea nodurilor(vârfurilor) | ||
+ | *U este o mulțime formată din **perechi ordonate** de elemente ale lui X,numită mulțimea arcelor | ||
+ | |||
+ | ====3.2 Structură==== | ||
+ | Într-un graf orientat, distingem: | ||
+ | * **gradul interior/intern** al unui nod: numărul de arce care intră în nod | ||
+ | | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | ====3.3 Reprezentare==== | ||
+ | **Matricea de adiacență** | ||
+ | *a[i,j] = 1 ,dacă ∃ arcul (i,j) în mulțimea U | ||
+ | | ||
+ | |||
+ | {{ :laboratoare: | ||
+ | |||
+ | \\ | ||
+ | |||
+ | Matricea **vârfuri-arce** este o matrice **B** cu n = |X| linii și m = |U| coloane,în care fiecare element **b[i,j]** este: | ||
+ | * **1** ,dacă nodul i este o extremitate inițială a arcului | ||
+ | * **-1** ,dacă nodul i este o extremitate finală a arcului | ||
+ | * **0** ,dacă nodul i nu este o extremitate a arcului | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | =====4 Parcurgerea grafurilor===== | ||
+ | ====4.1 Parcurgerea în lățime==== | ||
+ | |||
+ | Parcurgerea în lățime **(Breadth-First-Search -BFS)** este o metodă ce presupune vizitarea nodurilor în următoarea ordine: | ||
+ | * nodul sursă (considerat a fi pe nivelul 0) | ||
+ | * vecinii nodului sursă (reprezentând nivelul 1) | ||
+ | * vecinii încă nevizitați ai nodurilor de pe nivelul 1 (reprezentând nivelul 2) | ||
+ | * ș.a.m.d | ||
+ | |||
+ | |||
+ | ===4.1.1 Implementare=== | ||
+ | |||
+ | Pe masură ce algoritmul avansează, | ||
+ | * **alb** - nodul este nedescoperit încă | ||
+ | * **gri** - nodul a fost descoperit și este în curs de procesare | ||
+ | * **negru** - procesarea nodului s-a încheiat | ||
+ | Se păstrează informațiile despre distanța până la nodul sursă. | ||
+ | Se obține arborele BFS | ||
+ | |||
+ | \\ | ||
+ | Pentru implementarea BFS se utilizează o coadă (Q) în care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați, | ||
+ | |||
+ | <file cpp> | ||
+ | Pentru fiecare nod u din graf | ||
+ | { | ||
+ | | ||
+ | d[u] = infinit | ||
+ | p[u] = null // | ||
+ | } | ||
+ | |||
+ | culoare[sursă]=gri | ||
+ | d[sursă]=0 | ||
+ | enqueue(Q, | ||
+ | |||
+ | Cât timp coada Q nu este vidă | ||
+ | { | ||
+ | | ||
+ | | ||
+ | dacă culoare[u] == alb | ||
+ | { | ||
+ | | ||
+ | p[u] = v | ||
+ | d[u] = d[v] + 1 | ||
+ | | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | |||
+ | |||
+ | </ | ||
+ | \\ | ||
+ | **Exemplu** | ||
+ | {{ : | ||
+ | |||
+ | ====4.2 Parcurgerea în adâncime==== | ||
+ | Parcurgea în adâncime **(Depth-First-Search | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | *În momentul în care am epuizat vecinii unui nod //Vn//, continuăm cu următorul vecin nevizitat al nodului anterior,// | ||
+ | |||
+ | Această metoda de parcurgere pune prioritate pe explorarea **în adâncime** (pe distanțe tot mai mari față de nodul sursă). | ||
+ | |||
+ | ====4.2.1 Implementare==== | ||
+ | |||
+ | Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**, | ||
+ | |||
+ | <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ă) | ||
+ | |||
+ | </ | ||
+ | {{ : |