Teoria Grafurilor: Grafuri Neorientate – Metode de Reprezentare 19

---

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.