Teoria Grafurilor: Grafuri Neorientate – Noțiuni Introdutive și Parcurgerea în Adâncime (DFS) 21

---

1. Noțiuni introductive

---

Ce este un graf?

Un graf este o structură matematică care constă din:

• Noduri (sau vârfuri): Entitățile individuale din graf (VVV).
• Muchii: Legături între perechi de noduri (EEE).

---

Grafuri neorientate

Un graf neorientat este un graf în care muchiile nu au direcție, adică {u,v}={v,u}\{u, v\} = \{v, u\}{u,v}={v,u}.

Elemente fundamentale:

1. Noduri: Mulțimea VVV de noduri.
2. Muchii: Mulțimea EEE de perechi neordonate de noduri.
3. Gradul unui nod: Numărul de muchii care sunt incidente la un nod.

---

Reprezentarea grafurilor

1. Matrice de adiacență: Matrice binară A[i][j]A[i][j]A[i][j] care indică dacă există o muchie între nodurile iii și jjj.
2. Lista de adiacență: Fiecare nod are o listă de noduri adiacente.
3. Lista muchiilor: Fiecare muchie este reprezentată ca o pereche {u,v}\{u, v\}{u,v}.

---

2. Parcurgerea în adâncime (DFS)

---

Definiție:

DFS (Depth-First Search) explorează un graf mergând cât mai profund posibil pe fiecare ramură, înainte de a reveni și a explora alte ramuri.

---

Caracteristici:

• Utilizează o stivă pentru gestionarea nodurilor (recursiv sau explicit).
• Este utilă pentru:
  • Detectarea ciclurilor.
  • Determinarea componentelor conexe.
  • Generarea arborilor de parcurgere.

---

Algoritm general pentru DFS:

1. Pornim de la un nod inițial și îl marcăm ca vizitat.
2. Explorăm recursiv toți vecinii nevizitați ai nodului curent.
3. Repetăm procesul până când toate nodurile accesibile au fost vizitate.

---

Exemplu grafic:

Graful:

1–2

|   |

4–3

• Lista de adiacență:

1: 2, 4

2: 1, 3

3: 2, 4

4: 1, 3

• DFS(1): 1 → 2 → 3 → 4

---

3. Implementare DFS în C++

---

Cu lista de adiacență:

#include <iostream>

#include <vector>

using namespace std;

// Funcția DFS

void dfs(int nod, vector<int> lista[], vector<bool>& vizitat) {

    cout << nod + 1 << ” „; // Afișăm nodul curent

    vizitat[nod] = true; // Marcăm nodul ca vizitat

    // Vizităm vecinii nodului curent

    for (int vecin : lista[nod]) {

        if (!vizitat[vecin]) {

            dfs(vecin, lista, vizitat);

        }

    }

}

int main() {

    int n = 4; // Numărul de noduri

    vector<int> lista[4]; // Lista de adiacență

    // Adăugare muchii

    lista[0].push_back(1); lista[1].push_back(0); // Muchie 1-2

    lista[0].push_back(3); lista[3].push_back(0); // Muchie 1-4

    lista[1].push_back(2); lista[2].push_back(1); // Muchie 2-3

    lista[3].push_back(2); lista[2].push_back(3); // Muchie 4-3

    vector<bool> vizitat(n, false); // Inițial, niciun nod nu este vizitat

    cout << „DFS începe de la nodul 1: „;

    dfs(0, lista, vizitat);

    cout << endl;

    return 0;

}

---

Cu matrice de adiacență:

#include <iostream>

using namespace std;

void dfs(int nod, int n, int matrice[100][100], bool vizitat[]) {

    cout << nod + 1 << ” „; // Afișăm nodul curent

    vizitat[nod] = true; // Marcăm nodul ca vizitat

    for (int i = 0; i < n; i++) {

        if (matrice[nod][i] == 1 && !vizitat[i]) { // Dacă există muchie și nodul nu a fost vizitat

            dfs(i, n, matrice, vizitat);

        }

    }

}

int main() {

    int n = 4; // Numărul de noduri

    int matrice[100][100] = {0}; // Matricea de adiacență

    // Adăugare muchii

    matrice[0][1] = matrice[1][0] = 1; // Muchie 1-2

    matrice[0][3] = matrice[3][0] = 1; // Muchie 1-4

    matrice[1][2] = matrice[2][1] = 1; // Muchie 2-3

    matrice[3][2] = matrice[2][3] = 1; // Muchie 4-3

    bool vizitat[100] = {false}; // Inițial, niciun nod nu este vizitat

    cout << „DFS începe de la nodul 1: „;

    dfs(0, n, matrice, vizitat);

    cout << endl;

    return 0;

}

---

4. Aplicații practice ale DFS

1. Detectarea componentelor conexe:
   DFS poate determina numărul de subgrafuri conexe dintr-un graf.
2. Detectarea ciclurilor:
   DFS poate verifica dacă există cicluri într-un graf.
3. Colorarea grafurilor:
   DFS poate fi utilizat pentru colorarea nodurilor unui graf bipartit.
4. Generarea unui arbore de acoperire:
   DFS poate construi un arbore care conectează toate nodurile unui graf.

---

5. Activități practice pentru elevi

1. Scrieți o funcție care determină numărul de componente conexe ale unui graf folosind DFS.
2. Implementați o funcție care verifică dacă un graf conține un ciclu.
3. Extindeți implementarea DFS pentru a ține evidența ordinii de intrare și ieșire a nodurilor.

---

6. Avantaje și dezavantaje ale DFS

Avantaje	Dezavantaje
Eficient pentru explorarea completă	Poate consuma memorie mare pentru grafuri mari (stivă recursivă).
Ușor de implementat	Nu garantează cel mai scurt drum între noduri.
Util pentru grafuri dense

---

7. Concluzie

• Parcurgerea în adâncime (DFS) este o metodă fundamentală pentru explorarea grafului.
• Este utilă pentru detectarea conexiunilor, ciclurilor și generarea arborilor de parcurgere.
• Implementarea DFS în C++ este ușor de realizat și oferă o bază solidă pentru algoritmi mai avansați.