Pe scurt
Un graf neorientat este o pereche (V, E) cu muchii bidirecționale între noduri. Parcurgerile BFS și DFS sunt esențiale pentru explorarea grafurilor, iar componentele conexe reprezintă submulțimi maximale de noduri conectate între ele prin drumuri.
Reprezentarea grafurilor neorientate
Un graf neorientat este o pereche G = (V, E), unde
- V este o mulțime finită de noduri (vârfuri)
- E este o mulțime de muchii, fiecare muchie fiind o pereche neordonată de noduri
În graful neorientat, legătura dintre două noduri este bidirecțională.
Reprezentarea grafurilor în programare se face prin două metode principale
- Matricea de adiacență – matrice pătratică de dimensiune n x n, unde n = |V|, iar elementul a[i][j] = 1 dacă există muchie între nodurile i și j, altfel 0. Este utilă pentru grafuri dense, dar pentru grafuri rare este ineficientă din punct de vedere al memoriei.
- Lista de adiacență – folosește un vector de liste (sau vectori) pentru fiecare nod, în care se rețin vecinii acestuia. Este eficientă ca memorie pentru orice tip de graf.
Exemplul 1: Reprezentare cu liste de adiacență. Fie graful cu 4 noduri (0-3) și muchiile: (0,1), (1,2), (2,3). Lista: 0: [1], 1: [0,2], 2: [1,3], 3: [2].
Parcurgerea BFS (Breadth-First Search)
BFS explorează graful pe niveluri, plecând de la un nod sursă și vizitând toți vecinii acestuia, apoi vecinii vecinilor etc. Se implementează cu o coadă.
Caracteristici principale
- Găsește cel mai scurt drum (ca număr de muchii) între nodul sursă și orice alt nod
- Explorează sistematic, nivel cu nivel
Exemplul 1 (continuare): Parcurgerea BFS pornind din 0: ordinea vizitării = 0, 1, 2, 3.
Exemplul 3: Aplicarea BFS pentru găsirea celui mai scurt drum între nodul 0 și nodul 3 într-un graf în formă de linie: 0-1-2-3. Distanțe: d[0]=0, d[1]=1, d[2]=2, d[3]=3. Drumul minim de la 0 la 3 are 3 muchii.
Parcurgerea DFS (Depth-First Search)
DFS explorează în adâncime, plecând de la un nod sursă și mergând cât mai departe pe un drum, apoi se întoarce (backtracking). Se implementează recursiv sau cu o stivă.
Caracteristici principale
- Nu garantează găsirea celui mai scurt drum
- Explorează în profunzime înainte de a trece la altă ramură
Exemplul 1 (continuare): DFS (recursiv) ordinea = 0, 1, 2, 3.
Componente conexe
O componentă conexă a unui graf neorientat este un subgraf maximal în care orice două noduri sunt conectate printr-un drum.
Algoritmul de determinare a componentelor conexe
- Parcurgerea (BFS sau DFS) a fiecărui nod nevizitat
- Marcarea întregii componente
- Numărul de apeluri ale parcurgerii din main este egal cu numărul de componente conexe
Exemplul 2: Graf cu două componente conexe. Noduri: 0-4. Muchii: (0,1), (1,2) și (3,4). Componente: {0,1,2} și {3,4}. BFS din 0 vizitează 0,1,2; din 3 vizitează 3,4. Numărul de componente = 2.
Aplicații și importanță
Parcurgerile grafurilor sunt esențiale pentru
- Verificarea conexității
- Găsirea drumurilor
- Sortarea topologică
Aplicații practice
- Verificarea existenței unui drum între două noduri
- Planificarea rețelelor
- Detectarea insulelor
- Jocuri puzzle
La Bacalaureat, aceste concepte apar frecvent la subiectele de algoritmică, iar cunoașterea implementării eficiente este obligatorie.
Verifică-te!
- Care este diferența principală între BFS și DFS în ceea ce privește găsirea celui mai scurt drum între două noduri?
- Cum se determină numărul de componente conexe ale unui graf neorientat folosind parcurgeri?
- În ce situație este mai eficientă matricea de adiacență față de lista de adiacență pentru reprezentarea unui graf?