Teoria Grafurilor: Grafuri Neorientate – Parcurgerea Grafurilor 20

---

1. Obiectivele lecției:

• Să înțeleagă conceptele de parcurgere a grafurilor.
• Să învețe și să implementeze cele două metode principale de parcurgere:
  • Parcurgerea în adâncime (Depth-First Search – DFS).
  • Parcurgerea în lățime (Breadth-First Search – BFS).
• Să identifice aplicații practice ale parcurgerii grafurilor.

---

2. Ce este parcurgerea unui graf?

Parcurgerea unui graf reprezintă vizitarea tuturor nodurilor, urmând un anumit algoritm.
Aceasta poate fi utilizată pentru:

• Explorarea conexiunilor între noduri.
• Determinarea componentelor conexe.
• Găsirea unui drum între două noduri.

---

3. Metode principale de parcurgere

---

1. Parcurgerea în adâncime (DFS)

1. Definiție:
   DFS explorează un graf mergând cât mai profund posibil pe fiecare ramură, înainte de a reveni și a explora alte ramuri.
2. Pași generali:
   • Se vizitează nodul curent și se marchează ca vizitat.
   • Se recursă pe toți vecinii nodului curent care nu au fost încă vizitați.
3. Reprezentare grafică:

Exemplu:

    1–2

    |   |

    4–3

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

4. Implementare în C++ (cu lista de adiacență):

#include <iostream>

#include <vector>

using namespace std;

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

    cout << nod + 1 << ” „;

    vizitat[nod] = true;

    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;

}

---

2. Parcurgerea în lățime (BFS)

1. Definiție:
   BFS explorează un graf nivel cu nivel, pornind de la nodul inițial, și vizitează toți vecinii unui nod înainte de a trece la nivelul următor.
2. Pași generali:
   • Se adaugă nodul inițial într-o coadă și se marchează ca vizitat.
   • Se scoate nodul din coadă, se vizitează și se adaugă vecinii săi nevizitați în coadă.
3. Reprezentare grafică:

Exemplu:

    1–2

    |   |

    4–3

BFS(1): 1 → 2 → 4 → 3

4. Implementare în C++ (cu lista de adiacență):

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

void bfs(int start, vector<int> lista[], vector<bool>& vizitat) {

    queue<int> coada;

    coada.push(start);

    vizitat[start] = true;

    while (!coada.empty()) {

        int nod = coada.front();

        coada.pop();

        cout << nod + 1 << ” „;

        for (int vecin : lista[nod]) {

            if (!vizitat[vecin]) {

                coada.push(vecin);

                vizitat[vecin] = true;

            }

        }

    }

}

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 << „BFS începe de la nodul 1: „;

    bfs(0, lista, vizitat);

    cout << endl;

    return 0;

}

---

4. Compararea DFS și BFS

Caracteristică	DFS	BFS
Metodă	Explorează cât mai profund.	Explorează nivel cu nivel.
Structură utilizată	Stivă (implicit recursivitate).	Coadă.
Consum de memorie	Depinde de adâncimea arborelui.	Depinde de lățimea arborelui.
Aplicații	Detectare cicluri, parcurgerea labirintului.	Găsirea celui mai scurt drum într-un graf neponderat.

---

5. Aplicații practice ale parcurgerii grafurilor

1. DFS:
   • Detectarea componentelor conexe ale unui graf.
   • Detectarea ciclurilor într-un graf.
   • Parcurgerea labirinturilor.
2. BFS:
   • Găsirea celui mai scurt drum într-un graf neponderat.
   • Găsirea tuturor nodurilor accesibile dintr-un nod inițial.

---

6. Activități practice pentru elevi

1. Implementați un program care determină numărul de componente conexe ale unui graf folosind DFS.
2. Scrieți un program care determină dacă un graf este bipartit folosind BFS.
3. Extindeți implementările pentru a parcurge grafuri reprezentate prin matrice de adiacență.

---

7. Concluzie

• Parcurgerea grafurilor este o tehnică fundamentală în teoria grafurilor și are multiple aplicații practice.
• DFS este util pentru explorarea completă a unui graf, în timp ce BFS este ideal pentru determinarea drumurilor minime.
• Alegerea metodei potrivite depinde de problema pe care o rezolvăm.