Lecția Reprezentarea Grafurilor: Matrice de Adiacență, Listă de Adiacență și Matrice de Incidență

Grafurile sunt structuri de date fundamentale utilizate pentru a modela relații între obiecte. Ele constau din noduri (sau vârfuri) și muchii (sau arce).

1. Tipuri de Grafuri

1. Grafuri Neorientate:
   • Muchiile nu au direcție. Dacă există o muchie între A și B, se poate merge atât din A în B, cât și din B în A.
   • Exemplu: Relația de prietenie pe Facebook (dacă A este prieten cu B, atunci și B este prieten cu A).
2. Grafuri Orientate (Digrafuri):
   • Muchiile au direcție. Dacă există o muchie de la A la B, aceasta nu implică o legătură și de la B la A.
   • Exemplu: Urmărirea pe Instagram (A îl poate urmări pe B, dar B nu îl urmărește neapărat pe A).

---

2. Reprezentarea Grafurilor

Există mai multe metode pentru a reprezenta un graf în memorie. Cele mai utilizate sunt:

1. Matrice de Adiacență
2. Listă de Adiacență
3. Matrice de Incidență

---

2.1. Matrice de Adiacență

• O matrice pătratică în care:
  • mat[i][j] = 1 dacă există o muchie între nodurile i și j.
  • mat[i][j] = 0 dacă nu există muchie.
• Pentru grafuri neorientate, matricea este simetrică (mat[i][j] = mat[j][i]).
• Pentru grafuri orientate, matricea poate fi asimetrică.

---

Exemplu în C++ (Matrice de Adiacență)

#include <iostream>
using namespace std;

const int V = 4; // Numărul de noduri
int mat[V][V]; // Matrice de adiacență

// Funcție pentru a adăuga o muchie în graf neorientat
void addEdgeUndirected(int u, int v) {
    mat[u][v] = 1;
    mat[v][u] = 1;
}

// Funcție pentru a adăuga o muchie în graf orientat
void addEdgeDirected(int u, int v) {
    mat[u][v] = 1;
}

// Funcție pentru a afișa matricea de adiacență
void displayMatrix() {
    cout << "Matrice de adiacență:" << endl;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    // Inițializăm matricea cu 0
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            mat[i][j] = 0;
        }
    }

    // Adăugăm muchii pentru un graf neorientat
    addEdgeUndirected(0, 1);
    addEdgeUndirected(0, 2);
    addEdgeUndirected(1, 2);
    addEdgeUndirected(2, 3);

    // Afișăm matricea de adiacență
    displayMatrix();
    
    return 0;
}

Avantaje:

• Acces rapid pentru a verifica existența unei muchii: O(1).
• Simplu de implementat.

Dezavantaje:

• Necesită O(V^2) spațiu de memorie, chiar și pentru grafuri sparse.
• Ineficient pentru grafuri cu multe noduri și puține muchii.

---

2.2. Listă de Adiacență

• Fiecare nod are o listă de noduri adiacente (vecini).
• Se poate implementa cu vectori de vectori.
• Mai eficientă din punct de vedere al memoriei pentru grafuri sparse.

---

Exemplu în C++ (Listă de Adiacență)

#include <iostream>
#include <vector>
using namespace std;

const int V = 4; // Numărul de noduri
vector<int> adj[V]; // Listă de adiacență

// Funcție pentru a adăuga o muchie în graf neorientat
void addEdgeUndirected(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Funcție pentru a afișa lista de adiacență
void displayAdjList() {
    cout << "Lista de adiacență:" << endl;
    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (int j : adj[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
}

int main() {
    // Adăugăm muchii pentru un graf neorientat
    addEdgeUndirected(0, 1);
    addEdgeUndirected(0, 2);
    addEdgeUndirected(1, 2);
    addEdgeUndirected(2, 3);

    // Afișăm lista de adiacență
    displayAdjList();
    
    return 0;
}

Avantaje:

• Spațiu eficient: O(V + E), unde E este numărul de muchii.
• Eficient pentru parcurgerea vecinilor unui nod.

Dezavantaje:

• Verificarea existenței unei muchii necesită timp O(V) în cel mai rău caz.

---

2.3. Matrice de Incidență

• O matrice de dimensiune V x E, unde:
  • mat[i][j] = 1 dacă nodul i este incident cu muchia j.
  • mat[i][j] = 0 în caz contrar.

---

3. Alegerea Reprezentării Optime

• Matrice de Adiacență:
  • Ideală pentru grafuri dense (E ≈ V^2).
• Listă de Adiacență:
  • Ideală pentru grafuri sparse (E << V^2).
• Matrice de Incidență:
  • Folosită rar, în special în teorie sau aplicații specifice.

---

4. Concluzii

• Reprezentarea grafului depinde de densitatea acestuia și de operațiile necesare.
• Matricea de adiacență oferă acces rapid la existența muchiilor, dar consumă multă memorie.
• Lista de adiacență este mai eficientă pentru memorare și parcurgerea vecinilor unui nod.
• Matricea de incidență este mai puțin utilizată, dar oferă o perspectivă interesantă asupra relațiilor nod-muchie.