GRAFURI NEORIENTATE
Conform Wikipedia, “un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi, eventual, atribuite direcții (în acest caz, se spune că graful este orientat). Un graf poate fi reprezentat geometric ca o mulțime de puncte legate între ele prin linii (de obicei curbe).
Grafurile au o importanță imensă în informatică, de exemplu:
- în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf;
- schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;
- în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări).”
CUPRINS:
DEFINIŢII:
Un graf neorientat este o pereche ordonată de mulțimi G = (N, M), unde:
- N este o mulțime finită și nevidă de elemente numite noduri;
- M este o mulțime finită de submulțimi cu două elemente din N, numite muchii.
Nodurile se notează cu valori între 1 și n (unde n este numărul de noduri din graf, iar muchiile cu (x, y) sau [x, y], unde x și y sunt noduri și se numesc extremitățile muchiei. Vom nota numărul de muchii cu m.
Numerotarea nodurilor este la latitudinea utilizatorului.
Un vecin al unui nod x este orice nod y cu proprietatea că există muchia (x, y).
Două noduri între care există muchie se numesc adiacente.
Două muchii sunt incidente dacă au o extremitate comună. Un nod este incident cu o muchie dacă nodul este extremitate a acelei muchii.
Mulțimea muchiilor are proprietatea de simetrie: dacă (x, y) este muchie, atunci și (y, x) este muchie.
Prin definiție, într-un graf neorientat NU există muchie de la un nod la el însuși;
Fie graful din figura de mai jos:
Fig.1 Un prim exemplu de graf neorientat
Considerăm graful din figura 1.
Mulţimea N este atunci {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} (n = 12)
iar mulţimea M este {[1, 2], [3, 4], [7, 6], [7, 10], [10, 6], [9, 5], [9, 11]}
Numărul de muchii din exemplul dat este 7 (m = 7).
Două exemple de noduri adiacente: 6 şi 7, 9 şi 5.
Muchiile [4, 6] şi [7, 6] sunt incidente, având comun nodul 6.
Lanţ = succesiune de noduri L = [x1, x2, …, xk] cu proprietatea că două noduri consecutive din succesiune sunt adiacente. Nodurile x1 şi xk se numesc extremitățile lanțului. Nodul x1 se numeşte extremitatea iniţială, iar nodul x2 numeşte extremitatea finală. Numărul k-1 se numește lungimea lanțului și este numărul de muchii din care este format lanţul
Lanț simplu = un lanț care conține numai muchii distincte este
Lanț compus = un lanț în care muchiile nu sunt distincte
Ciclu = lanț simplu în care primul nod este identic cu ultimul
Ciclu elementar = ciclu în care toate nodurile sunt distincte, mai puțin primul și ultimul
Fig.2 Un alt exemplu de graf neorientat
Ciclu hamiltonian = ciclu elementar care conține toate nodurile grafului
Graf hamiltonian = graf care conține un ciclu hamiltonian
Ciclu eulerian = ciclu care conține toate muchiile grafului
Graf eulerian = graf care conține un ciclu eulerian
Fig.3 Al treilea exemplu de graf neorientat ("problema Comis Voiajorului")
Gradul al unui nod este numărul de noduri adiacente cu acesta (sau numărul de muchii incidente cu acesta). Gradul unui nod x se notează cu d(x) (degree).
Pentru graful din figura 1, gradele nodurilor sunt date în tabelul:
x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
d(x) |
1 |
1 |
1 |
2 |
1 |
3 |
2 |
0 |
2 |
2 |
1 |
0 |
Suma gradelor tuturor nodurilor dintr-un graf este totdeauna egală cu dublul numărului de muchii.
În exemplul nostru, 1 + 1 + 1 + 2 + 1 + 3 + 2 + 0 + 2 + 2 + 1 + 0 = 16 = 2 * m = 2 * 8 = 16.
Un nod care are gradul 0 se numeşte nod izolat.
În exemplul din figura 1, nodurile 8 şi 12 sunt noduri izolate.
Un nod care are gradul 1, se numeşte nod terminal.
În exemplul de mai sus, nodurile 1, 2, 3, 5 şi 11 sunt noduri terminale.
Numim graf complet un graf în care oricare două noduri distincte sunt adiacente.
Un graf complet care are n noduri se notează cu Kn .
Mai jos sunt reprezentate grafurile complete K3 şi K4 :
Un graf complet cu n noduri are 
muchii .
Într-un graf complet cu n noduri, gradul fiecărui nod este n-1, iar suma gradelor tuturor nodurilor este S = n*(n-1).
Un graf neorientat se numește graf nul, dacă mulțimea muchiilor este vidă. Într-un graf nul toate nodurile sunt izolate.
Definiție: Un graf neorientat se numește graf conex dacă pentru oricare două vârfuri x și y diferite ale sale, există cel puțin un lanț care le leagă, adică x este extremitatea inițială și y este extremitatea finală
Un graf cu un singur nod este, prin definiție, conex
Definiție: Se numește componentă conexă a unui graf G=(N,M) un subgraf H=(Y, V), conex, al lui G care are proprietatea că nu există nici un lanț în G care să lege un vârf din Y cu un vârf din X – Y
REPREZENTAREA GRAFURILOR NEORIENTATE
A. Matricea de adiacenţă
Matricea de adiacenţă asociată grafului G = (X, M), este o matrice pătratică de ordinul n, notată ma[ ][ ], ale cărei elemente sunt definite astfel:
Pentru graful din figura 1, matricea de adiacenţă este:
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | |
| 01 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 02 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 03 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 04 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 06 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 07 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 08 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 09 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Pentru graful din figura 2, matricea de adiacenţă este:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 5 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 7 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Pentru graful din figura 3, matricea de adiacenţă este:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 1 | 1 | 1 |
| 4 | 0 | 0 | 1 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 1 | 0 | 1 |
| 6 | 1 | 1 | 1 | 0 | 1 | 0 |
B. Matricea muchiilor
Matricea muchiilor asociată grafului G = (X, M), este o matrice, în general nepătratică de dimensiune m(m fiind numărul de muchii din graf), matrice notată mm[ ][ ], ale cărei elemente sunt definite astfel:
Pentru graful din figura 1, matricea muchiilor este:
| x | y | |
| 1 | 1 | 2 |
| 2 | 3 | 4 |
| 3 | 7 | 6 |
| 4 | 7 | 10 |
| 5 | 10 | 6 |
| 6 | 9 | 5 |
| 7 | 9 | 11 |
Pentru graful din figura 2, matricea muchiilor este:
| x | y | |
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 4 |
| 4 | 4 | 5 |
| 5 | 5 | 1 |
| 6 | 1 | 4 |
| 7 | 2 | 6 |
| 8 | 6 | 7 |
| 9 | 7 | 2 |
Pentru graful din figura 3, matricea muchiilor este:
| x | y | |
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 4 |
| 4 | 4 | 5 |
| 5 | 5 | 6 |
| 6 | 6 | 1 |
| 7 | 2 | 5 |
| 8 | 2 | 6 |
| 9 | 3 | 5 |
| 10 | 3 | 6 |
C. Listele de adiacenţă
- 1: 2
- 2: 1
- 3: 4
- 4: 3
- 5: 9
- 6: 7 10
- 7: 6 10
- 8:
- 9: 5 11
- 10: 6 7
- 11: 9
- 12:
PARCURGEREA GRAFURILOR NEORIENTATE
Parcurgerea grafurilor mai este numită străbaterea grafurilor, sau traversarea grafurilor
A. Parcurgerea în lăţime
Fig.4 Al patrulea exemplu de graf neorientat
Vom utiliza o coadă şi un c[ ] de lungime 9, care ne va furniza, în final, ordinea de vizitare a nodurilor şi un vector v[ ] de lungime 9, care reţine pe poziţia i valoarea 0 (dacă nodul i nu a fost încă vizitat) sau 1 (dacă nodul i a fost deja vizitat).
La început, vectorul v[ ] se iniţializează la 0.
Presupunem că alegem 4 ca nod de plecare.
Valoarea 4 se introduce pe prima poziţie în coadă (c[1] = 4); nodul 4 se marchează ca vizitat (se pune valoara 1 pe poziţia 4 din vectorul v[ ] => v[4] = 1); markerul de început al cozii se pune pe pozţia 1 (ic =1); markerul de sfârşit al cozii se pune tot pe poziţia 1 (sc = 1).
Situaţia este, în acest moment:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| c | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Din acest moment porneşte algoritmul de parcurgere, care funcţionează cât timp ic (markerul de început al cozii) este mai mic sau egal cu sc (markerul de sfârşit al cozii).
Urmărind evoluţia algoritmului, se poate vedea că se pretează la o implementare recursivă.
Markerul de început al cozii fiind 1 (ic = 1), iar c[if] = c[1] = 4, se caută toate nodurile adiacente cu nodul 4 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem un singur nod adiacent cu nodul 4 şi anume nodul 9, care nu a fost vizitat (căci v[9] = 0). Se introduce nodul 9 în coadă, pe o nouă poziţie – markerul sf de sfârşit al cozii se deplasează spre dreapta (sc++; deci sc devine 2; c[sc] = c[2] = 9). Se marchează nodul 9 ca fiind vizitat (v[9] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Nemaifiind vecini nevizitaţi ai nodului 4, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 2;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 2 (ic = 2), iar c[if] = c[2] = 9, se caută toate nodurile adiacente cu nodul 9 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem două noduri adiacente cu nodul 9 şi anume nodulrile 4 şi 5, dar, consultând vectorul v[ ], constatăm că nodul 4 a fost deja vizitat (căci v[4] = 1), deci nu rămâne decât nodul 5 de introdus în coadă. Se introduce 5 în coadă (sc++; deci sc devine 3; c[sc] = c[3] = 5); se marchează nodul 5 ca fiind vizitat (v[5] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Nemaifiind vecini nevizitaţi ai nodului 9, mrkerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 3;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 3 (ic = 3), iar c[ic] = c[3] = 5, se caută toate nodurile adiacente cu nodul 5 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem patru noduri adiacente cu nodul 5: 6, 1, 9 şi 3, dar, consultând vectorul v[ ], constatăm că nodul 9 a fost deja vizitat (căci v[9] = 1), deci nu rămân decât nodurile 6, 1 şi 3 de introdus în coadă (ordinea în care le introducem este indiferentă; orice alegere este la fel de bună).
Se introduce nodul 6 în coadă (sc++; deci sc devine 4; c[sc] = c[4] = 6); se marchează nodul 6 ca fiind vizitat (v[6] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 0 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Se introduce nodul 1 în coadă (sc++; deci sc devine 5; c[sc] = c[5] = 1); se marchează nodul 1 ca fiind vizitat (v[1] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 0 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Se introduce nodul 3 în coadă (sc++; deci sc devine 6; c[sc] = c[6] =3 ); se marchează nodul 3 ca fiind vizitat (v[3] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 3 | 1 | 1 | 1 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Nemaifiind vecini nevizitaţi ai nodului 5, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 4;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 0 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 4 (ic = 4), iar c[ic] = c[4] = 6, se caută toate nodurile adiacente cu nodul 6 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem patru noduri adiacente cu nodul 6: 5, 1, 7 şi 8, dar, consultând vectorul v[ ], constatăm că nodurile 5 şi 1 au fost deja vizitate (căci v[5] = 1 şi v[1] = 1), deci nu rămân decât nodurile 7 şi 8 de introdus în coadă (ordinea în care le introducem este indiferentă; orice alegere este la fel de bună).Se introduce nodul 7 în coadă (sc++; deci sc devine 7; c[sc] = c[7] = 7); se marchează nodul 7 ca fiind vizitat (v[7] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 0 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Se introduce nodul 8 în coadă (sc++; deci sc devine 8; c[sc] = c[8] = 8); se marchează nodul 8 ca fiind vizitat (v[8] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Nemaifiind vecini nevizitaţi ai nodului 6, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 5;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 5 (ic = 5), iar c[ic] = c[5] = 1, se caută toate nodurile adiacente cu nodul 1 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem două noduri adiacente cu nodul 1 şi anume nodulrile 5 şi 6, dar, consultând vectorul v[ ], constatăm că ambele noduri au fost deja vizitate (căci v[5] = 1 şi v[6] = 1), deci nu rămâne nici un nod de introdus în coadă.
Nemaifiind vecini nevizitaţi ai nodului 1, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 6;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 0 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 6 (ic = 5), iar c[ic] = c[6] = 3, se caută toate nodurile adiacente cu nodul 3 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem două noduri adiacente cu nodul 3 şi anume nodulrile 5 şi 2, dar, consultând vectorul v[ ], constatăm că nodul 5 a fost deja vizitat (căci v[5] = 1), deci rămâne doar nodul 2 de introdus în coadă.
Se introduce nodul 2 în coadă (sc++; deci sc devine 9; c[sc] = c[9] = 2); se marchează nodul 2 ca fiind vizitat (v[2] = 1).
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 2 |
| ic | ↑ | ||||||||
| sc | ↑ |
Nemaifiind vecini nevizitaţi ai nodului 3, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 7;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 2 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 7 (ic = 7), iar c[ic] = c[7] = 7, se caută toate nodurile adiacente cu nodul 7 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem două noduri adiacente cu nodul 7 şi anume nodulrile 6 şi 8, dar, consultând vectorul v[ ], constatăm că ambele noduri au fost deja vizitate (căci v[6] = 1 şi v[8] = 1), deci nu rămâne nici un nod de introdus în coadă.
Nemaifiind vecini nevizitaţi ai nodului 7, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 8;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 2 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 8 (ic = 8), iar c[ic] = c[8] = 8, se caută toate nodurile adiacente cu nodul 8 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem două noduri adiacente cu nodul 8 şi anume nodulrile 6 şi 7, dar, consultând vectorul v[ ], constatăm că ambele noduri au fost deja vizitate (căci v[6] = 1 şi v[7] = 1), deci nu rămâne nici un nod de introdus în coadă.
Nemaifiind vecini nevizitaţi ai nodului 8, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 9;
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| v[i] | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c[i] | 4 | 9 | 5 | 6 | 1 | 3 | 7 | 8 | 2 |
| ic | ↑ | ||||||||
| sc | ↑ |
Markerul de început al cozii fiind 9 (ic = 9), iar c[ic] = c[9] = 2, se caută toate nodurile adiacente cu nodul 2 (nevizitate încă), pentru a fi introduce în coadă.
În cazul de faţă, avem un singur nod adiacent cu nodul 2 şi anume nodul 3, care a fost deja vizitat (căci v[2] = 1), deci nu rămâne nici un nodde introdus în coadă.
Nemaifiind vecini nevizitaţi ai nodului 2, markerul de început al cozii se deplasează spre dreapta (ic++). Deci, acum, ic = 10;
În acest moment, markerul de început al cozii (ic = 10) a devenit mai mare decât markerul de sfârşit al cozii (sc = 9) şi algoritmul se opreşte.
Parcurgând coada c [ ], obţinem succesiunea nodurilor pentru graful considerat, în cazul străbaterii în lăţime, pornind din nodul 4: 4, 9, 5, 6, 1, 3, 7, 8, 2
B. Parcurgerea în adâncime
EXEMPLE DE APLICAŢII PENTRU EXPLOATAREA GRAFURILOR NEORIENTATE
A. Străbarea grafurilor neorientate
Exemplul 1:
Pentru graful din figura
-
Fig.5 Caz special de graf neorientat = arbore
(care este, de fapt, un arbore) avem fisierul “arcgrf1.in”, cu următorul conţiunut:
14 13
1 2
1 3
1 4
2 5
2 6
5 10
4 7
4 8
4 9
7 11
9 12
9 13
12 14
se obţin rezultatele:
O variantă on-line poate fi experimentată la strabatGraf
Exemplul 2:
Pentru graful din figura 2
avem fisierul “arcgrf2.in”, cu următorul conţiunut:
7 9
1 2
2 3
3 4
4 5
5 1
1 4
2 7
7 6
6 2
Exemplul 3:
Pentru graful din figura 3, (exemplu clasic pentru “Problema Comis-Voiajorului”)
avem fisierul “arcgrf3.in”, cu următorul conţiunut:
6 10
1 2
2 3
3 4
4 5
5 6
6 1
2 6
3 5
2 5
3 6
se obţin rezultatele:
O variantă on-line poate fi experimentată la
Exemplul 4:
Utilizam graful din figura 4.
Graful are nouă noduri (n = 9) şi 10 muchii (m = 10). Matricea muchiilor este conţinută în fişierul “arcgrf4.in” având conţinutul:
9 10
2 3
3 5
4 9
5 9
5 1
5 6
1 6
6 8
6 7
7 8
B. Determinarea unui ciclu hamiltonian
Vom utiliza din nou graful din figura 3 "problema comis voiajorului", pe care o prezentam, fara a o mai renumerota.
O variantă on-line poate fi experimentată la comisVoiajor