|

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

  1. 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.
  2. 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.
  3. Grafuri ponderate:
    • În loc de valori binare (0 și 1), matricea conține greutățile muchiilor sau arcelor.

4. Avantaje și Dezavantaje

AvantajeDezavantaje
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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *