Grafuri neorientate (reprezentare, parcurgeri DFS/BFS, componente conexe)

Un graf neorientat este o pereche ordonata G = (V, U), unde V este o multime finita de noduri (varfuri), iar U este o multime de muchii, fiecare muchie fiind o pereche neordonata de noduri distincte. Muchiile nu au directie, ceea ce inseamna ca (u, v) este identic cu (v, u). Reprezentarea in memorie se face frecvent prin matrice de adiacenta (o matrice patratica cu n linii si n coloane, unde elementul a[i][j] = 1 daca exista muchie intre nodurile i si j, altfel 0) sau prin liste de adiacenta (un vector de liste, fiecare lista continand vecinii nodului respectiv).

Parcurgerea unui graf inseamna vizitarea sistematica a tuturor nodurilor accesibile, folosind reguli precise. Depth-First Search (DFS) exploreaza pe cat posibil in adancime, mergand de la un nod la un vecin nevizitat, apoi inapoi cand nu mai exista vecini nevizitati. DFS se implementeaza recursiv sau cu o stiva.

Breadth-First Search (BFS) exploreaza in latime, vizitand toate nodurile la aceeasi distanta de nodul de plecare inainte de a trece la nivelul urmator. BFS se implementeaza cu o coada. Componentele conexe ale unui graf neorientat sunt subgrafuri maximale in care orice doua noduri sunt unite printr-un lant.

Pentru a le determina, se porneste o parcurgere (DFS sau BFS) de la fiecare nod nevizitat si se marcheaza toate nodurile accesibile ca apartinand aceleiasi componente. Complexitatea de timp pentru ambele parcurgeri, folosind liste de adiacenta, este O(n + m), unde n = numarul de noduri, m = numarul de muchii. Aplicatii: detectarea ciclurilor, sortarea topologica (pe grafuri orientate), determinarea bipartitiei, algoritmi de drum minim (BFS pentru grafuri neponderate).

In context bacalaureat, se cere implementarea eficienta a parcurgerilor si identificarea componentelor conexe. Se recomanda utilizarea listelor de adiacenta pentru grafuri rare. Pentru grafuri dese, matricea de adiacenta poate fi mai simpla.

Antrenamentul pe probleme clasice (cum ar fi numararea componentelor, verificarea conexitatii, determinarea distantei minime) este esential.

Exemple

• Exemplul 1: Reprezentarea unui graf cu 5 noduri si muchiile (1,2), (1,3), (2,4), (3,4), (4,5) prin matrice de adiacenta: matricea 5x5 cu 1 pe pozitiile (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2), (4,3), (4,5), (5,4) si 0 in rest. Observam simetria fata de diagonala principala.
• Exemplul 2: Parcurgere DFS pornind din nodul 1 pentru acelasi graf. Se viziteaza 1, apoi un vecin (de ex. 2), din 2 se merge la 4, din 4 la 3 (nevizitat), din 4 la 5 (nevizitat). Se marcheaza toate nodurile ca vizitate. Ordinea de vizitare: 1,2,4,3,5 (sau varianta 1,3,4,2,5 in functie de ordinea vecinilor).
• Exemplul 3: Parcurgere BFS pornind din nodul 1 pentru acelasi graf. Se adauga 1 in coada, se viziteaza vecinii 2 si 3, apoi se extrag 2 si se viziteaza vecinul 4 (nevizitat), apoi se extrage 3 (vecinii sunt deja vizitati sau in coada), se extrage 4 si se viziteaza 5. Ordinea: 1,2,3,4,5.

Concepte cheie: Graf neorientat: definitie, noduri, muchii, fara directie, Reprezentare: matrice de adiacenta (O(n^2) memorie) vs liste de adiacenta (O(n+m) memorie), Parcurgere DFS: algoritm recursiv sau cu stiva, complexitate O(n+m), utilizat pentru detectarea componentelor conexe, cicluri, bipartitie, Parcurgere BFS: algoritm cu coada, complexitate O(n+m), utilizeaza distanta minima in grafuri neponderate, Componente conexe: subgrafuri maximale conexe, determinare prin parcurgeri multiple, Aplicatii: numararea componentelor, verificarea conexitatii, drum minim (BFS), sortare topologica (pe orientate)