Metode de Reprezentare a Grafurilor: Matricea de Adiacență 25
1. Ce este Matricea de Adiacență?
Matricea de adiacență este o metodă de reprezentare a unui graf (neorientat sau orientat) folosind o matrice binară AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de noduri din graf.
2. Definiție
Pentru un graf G=(V,E)G = (V, E)G=(V,E):
- A[i][j]=1A[i][j] = 1A[i][j]=1, dacă există o muchie (sau un arc, în cazul grafurilor orientate) între nodurile iii și jjj.
- A[i][j]=0A[i][j] = 0A[i][j]=0, altfel.
3. Caracteristici
- Grafuri neorientate:
- Matricea este simetrică (A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]).
- Elementele de pe diagonala principală (A[i][i]A[i][i]A[i][i]) sunt 0 pentru grafuri fără bucle.
- Grafuri orientate:
- Matricea poate fi asimetrică (A[i][j]≠A[j][i]A[i][j] \neq A[j][i]A[i][j]=A[j][i]).
- A[i][j]=1A[i][j] = 1A[i][j]=1 indică un arc orientat de la iii la jjj.
- Grafuri ponderate:
- În loc de valori binare (0 și 1), matricea conține greutățile muchiilor sau arcelor.
4. Avantaje și Dezavantaje
Avantaje | Dezavantaje |
Acces rapid pentru verificarea existenței unei muchii (O(1)O(1)O(1)). | Necesită ( O( |
Ușor de implementat și de utilizat. | Complexitatea spațială crește odată cu numărul de noduri. |
Reprezentare simplă pentru grafuri dense. | Traversarea vecinilor unui nod necesită ( O( |
5. Exemplu pentru Grafuri Neorientate
Graf:
1–2
| |
4–3
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Muchii: E={(1,2),(1,4),(2,3),(3,4)}E = \{(1, 2), (1, 4), (2, 3), (3, 4)\}E={(1,2),(1,4),(2,3),(3,4)}
Matricea de adiacență:
1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0
6. Exemplu pentru Grafuri Orientate
Graf:
(1) → (2)
↑ ↓
(4) ← (3)
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Arce: E={(1,2),(3,4),(4,1),(2,3)}E = \{(1, 2), (3, 4), (4, 1), (2, 3)\}E={(1,2),(3,4),(4,1),(2,3)}
Matricea de adiacență:
1 2 3 4
1 0 1 0 0
2 0 0 1 0
3 0 0 0 1
4 1 0 0 0
7. Exemplu pentru Grafuri Ponderate
Graf:
1–2 (5)
| |
(3) (2)
| |
3–4 (4)
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Muchii cu greutăți: E={(1,2,5),(1,3,3),(2,4,2),(3,4,4)}E = \{(1, 2, 5), (1, 3, 3), (2, 4, 2), (3, 4, 4)\}E={(1,2,5),(1,3,3),(2,4,2),(3,4,4)}
Matricea de adiacență:
1 2 3 4
1 0 5 3 0
2 5 0 0 2
3 3 0 0 4
4 0 2 4 0
8. Implementare în C++
1. Matricea de adiacență pentru graf neorientat
#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; // Numărul de noduri
int matrice[100][100] = {0};
// 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
cout << „Matricea de adiacență pentru graful neorientat:\n”;
afisareMatrice(n, matrice);
return 0;
}
2. Matricea de adiacență pentru graf orientat
#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; // Numărul de noduri
int matrice[100][100] = {0};
// Adăugare arce
matrice[0][1] = 1; // Arc 1 → 2
matrice[1][2] = 1; // Arc 2 → 3
matrice[2][3] = 1; // Arc 3 → 4
matrice[3][0] = 1; // Arc 4 → 1
cout << „Matricea de adiacență pentru graful orientat:\n”;
afisareMatrice(n, matrice);
return 0;
}
3. Matricea de adiacență pentru graf ponderat
#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; // Numărul de noduri
int matrice[100][100] = {0};
// Adăugare muchii ponderate
matrice[0][1] = 5; // Muchie 1-2 cu greutatea 5
matrice[0][2] = 3; // Muchie 1-3 cu greutatea 3
matrice[1][3] = 2; // Muchie 2-4 cu greutatea 2
matrice[2][3] = 4; // Muchie 3-4 cu greutatea 4
cout << „Matricea de adiacență pentru graful ponderat:\n”;
afisareMatrice(n, matrice);
return 0;
}
9. Concluzie
- Matricea de adiacență este o metodă simplă și eficientă pentru reprezentarea grafurilor dense.
- Este utilă pentru verificarea rapidă a existenței unei muchii.
- Pentru grafuri sparse, poate fi mai avantajos să se folosească lista de adiacență datorită economiei de memorie.