Teoria Grafurilor: Grafuri Neorientate – Metode de Reprezentare

---

1. Obiectivele lecției:

• Să înțeleagă metodele comune de reprezentare a grafurilor neorientate.
• Să compare avantajele și dezavantajele fiecărei metode.
• Să implementeze fiecare metodă în C++ pentru grafuri neorientate.

---

2. Ce este un graf neorientat?

Un graf neorientat este definit prin:

• Noduri (vârfuri): Setul VVV de entități distincte.
• Muchii: Setul EEE de perechi neordonate {u,v}\{u, v\}{u,v}, unde uuu și vvv sunt noduri.

---

3. Metode de reprezentare a grafurilor

---

1. Matricea de adiacență

1. Definiție:
   Matricea de adiacență este o matrice AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde:
   • A[i][j]=1A[i][j] = 1A[i][j]=1, dacă există o muchie între nodurile iii și jjj.
   • A[i][j]=0A[i][j] = 0A[i][j]=0, altfel.
2. Caracteristici:
   • Matricea este simetrică pentru grafuri neorientate (A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]).
   • Diagonala principală este zero în cazul în care nu există bucle (A[i][i]=0A[i][i] = 0A[i][i]=0).
3. Avantaje:
   • Reprezentare simplă și acces rapid (O(1)O(1)O(1)) pentru verificarea existenței unei muchii.
4. Dezavantaje:
   • Consumă O(∣V∣2)O(|V|^2)O(∣V∣2) memorie, ineficient pentru grafuri sparse.
5. Exemplu: Graful:

1–2

|   |

3–4

Matricea de adiacență:

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

6. Implementare în C++:

#include <iostream>

using namespace std;

void afisareMatrice(int n, int matrice[100][100]) {

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

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

            cout << matrice[i][j] << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4;

    int matrice[100][100] = {0};

    // Adăugare muchii

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

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

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

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

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

    // Afișare matrice de adiacență

    afisareMatrice(n, matrice);

    return 0;

}

---

2. Lista de adiacență

1. Definiție:
   Fiecare nod este asociat cu o listă care conține toate nodurile adiacente acestuia.
2. Caracteristici:
   • Este eficientă pentru grafuri sparse.
   • Necesită spațiu O(∣V∣+∣E∣)O(|V| + |E|)O(∣V∣+∣E∣).
3. Avantaje:
   • Consum de memorie redus pentru grafuri sparse.
   • Traversarea vecinilor unui nod este rapidă.
4. Dezavantaje:
   • Verificarea existenței unei muchii necesită timp O(d(u))O(d(u))O(d(u)), unde d(u)d(u)d(u) este gradul nodului.
5. Exemplu: Graful:

1–2

|   |

3–4

Lista de adiacență:

1: 2, 3, 4

2: 1, 4

3: 1, 4

4: 1, 2, 3

6. Implementare în C++:

#include <iostream>

#include <vector>

using namespace std;

void afisareListaAdiacenta(int n, vector<int> lista[]) {

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

        cout << i + 1 << „: „;

        for (int vecin : lista[i]) {

            cout << vecin + 1 << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4;

    vector<int> lista[100];

    // Adăugare muchii

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

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

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

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

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

    // Afișare lista de adiacență

    afisareListaAdiacenta(n, lista);

    return 0;

}

---

3. Lista muchiilor

1. Definiție:
   Fiecare muchie este reprezentată ca o pereche (u,v)(u, v)(u,v), unde uuu și vvv sunt nodurile conectate.
2. Caracteristici:
   • Simplu de implementat.
   • Necesar pentru algoritmi care operează direct pe muchii.
3. Avantaje:
   • Eficientă pentru grafuri dense.
   • Utilă pentru algoritmi care necesită sortarea muchiilor (ex.: Kruskal).
4. Dezavantaje:
   • Traversarea vecinilor unui nod necesită timp O(∣E∣)O(|E|)O(∣E∣).
5. Exemplu: Graful:

1–2

|   |

3–4

Lista muchiilor:

(1, 2), (1, 3), (1, 4), (2, 4), (3, 4)

6. Implementare în C++:

#include <iostream>

#include <vector>

using namespace std;

void afisareListaMuchii(vector<pair<int, int>>& muchii) {

    for (auto muchie : muchii) {

        cout << „(” << muchie.first + 1 << „, ” << muchie.second + 1 << „) „;

    }

    cout << endl;

}

int main() {

    vector<pair<int, int>> muchii;

    // Adăugare muchii

    muchii.push_back({0, 1}); // Muchie 1-2

    muchii.push_back({0, 2}); // Muchie 1-3

    muchii.push_back({0, 3}); // Muchie 1-4

    muchii.push_back({1, 3}); // Muchie 2-4

    muchii.push_back({2, 3}); // Muchie 3-4

    // Afișare lista de muchii

    afisareListaMuchii(muchii);

    return 0;

}

---

4. Compararea metodelor de reprezentare

Metodă	Spațiu	Verificare muchie	Traversare vecini	Aplicații
Matrice de adiacență	( O(	V	^2) )	O(1)O(1)O(1)
Lista de adiacență	( O(	V	+	E
Lista muchiilor	( O(	E	) )	( O(

---

5. Activități practice pentru elevi

1. Implementați un program care convertește o matrice de adiacență într-o listă de adiacență.
2. Scrieți o funcție care determină dacă un graf reprezentat printr-o listă de adiacență este complet.
3. Implementați funcții de traversare (DFS, BFS) pentru grafuri reprezentate prin fiecare metodă.

---

6. Concluzie

• Reprezentarea unui graf depinde de tipul de aplicație și de caracteristicile grafului (dense/sparse).
• Matricea de adiacență este ideală pentru grafuri dense, în timp ce lista de adiacență este mai eficientă pentru grafuri sparse.
• Alegerea metodei potrivite optimizează atât consumul de memorie, cât și timpul de execuție al algoritmilor.

Teoria Grafurilor: Grafuri Neorientate – Parcurgerea Grafurilor

---

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.

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

---

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.