Metode de Reprezentare a Grafurilor: Lista Arcelor 28

---

1. Ce este Lista Arcelor?

Lista arcelor este o metodă de reprezentare a unui graf (neorientat sau orientat) printr-o listă de perechi care descriu conexiunile dintre noduri. Această metodă este utilă pentru a stoca și prelucra graful într-un mod eficient, mai ales atunci când graful este sparse (cu puține conexiuni comparativ cu numărul de noduri).

---

2. Structura Listei Arcelor

1. Noduri: Se presupune că nodurile sunt numerotate sau denumite distinct.
2. Arce/Muchii: O listă de perechi (u,v)(u, v)(u,v), unde uuu și vvv sunt noduri conectate:
   • Pentru grafuri neorientate, (u,v)(u, v)(u,v) și (v,u)(v, u)(v,u) sunt considerate echivalente.
   • Pentru grafuri orientate, direcția contează: (u,v)≠(v,u)(u, v) \neq (v, u)(u,v)=(v,u).
3. Opțional: Se pot adăuga greutăți pentru muchii/arce, reprezentându-le astfel sub forma (u,v,w)(u, v, w)(u,v,w), unde www este greutatea.

---

3. Avantaje și Dezavantaje

Avantaje	Dezavantaje
Consum redus de memorie pentru grafuri sparse.	Accesarea vecinilor unui nod necesită parcurgerea întregii liste.
Ușor de manipulat și sortat (ex.: pentru algoritmul Kruskal).	Nu este eficient pentru grafuri dense.
Ideală pentru grafuri orientate și ponderate.	Traversarea grafului poate fi mai complexă.

---

4. Exemplu pentru Grafuri

---

Graf Neorientat

Graful:

1–2

|   |

4–3

Lista arcelor:

E = {(1, 2), (1, 4), (2, 3), (3, 4)}

---

Graf Orientat

Graful:

(1) → (2)

 ↑      ↓

(4) ← (3)

Lista arcelor:

E = {(1, 2), (3, 4), (4, 1), (2, 3)}

---

Graf Ponderat

Graful:

1–2 (5)

|   |

(3) (2)

|   |

3–4 (4)

Lista arcelor:

E = {(1, 2, 5), (1, 3, 3), (2, 4, 2), (3, 4, 4)}

---

5. Implementare în C++

---

1. Reprezentare a arcelor pentru graf neorientat

#include <iostream>

#include <vector>

using namespace std;

int main() {

    // Lista arcelor

    vector<pair<int, int>> muchii = {

        {1, 2},

        {1, 4},

        {2, 3},

        {3, 4}

    };

    // Afișare lista arcelor

    cout << „Muchiile grafului sunt:\n”;

    for (auto muchie : muchii) {

        cout << „(” << muchie.first << „, ” << muchie.second << „)\n”;

    }

    return 0;

}

---

2. Reprezentare a arcelor pentru graf orientat

#include <iostream>

#include <vector>

using namespace std;

int main() {

    // Lista arcelor

    vector<pair<int, int>> arce = {

        {1, 2},

        {3, 4},

        {4, 1},

        {2, 3}

    };

    // Afișare lista arcelor

    cout << „Arcele grafului sunt:\n”;

    for (auto arc : arce) {

        cout << „(” << arc.first << ” → ” << arc.second << „)\n”;

    }

    return 0;

}

---

3. Reprezentare a arcelor pentru graf ponderat

#include <iostream>

#include <vector>

using namespace std;

int main() {

    // Lista arcelor ponderate

    vector<tuple<int, int, int>> arce = {

        {1, 2, 5},

        {1, 3, 3},

        {2, 4, 2},

        {3, 4, 4}

    };

    // Afișare lista arcelor ponderate

    cout << „Arcele grafului ponderat sunt:\n”;

    for (auto arc : arce) {

        cout << „(” << get<0>(arc) << „, ” << get<1>(arc) << „, ” << get<2>(arc) << „)\n”;

    }

    return 0;

}

---

6. Aplicații ale Listei Arcelor

1. Algoritmul Kruskal:
   Lista arcelor este utilizată pentru a găsi arborele de acoperire minimă prin sortarea arcelor după greutate.
2. Rețele și grafuri ponderate:
   Lista arcelor este esențială pentru problemele de flux sau drumuri minime.
3. Detectarea ciclurilor:
   Prin analizarea conexiunilor dintre noduri, se pot identifica cicluri.

---

7. Compararea Listei Arcelor cu Alte Metode

Metodă	Memorie	Complexitate acces vecini	Aplicații tipice
Lista Arcelor	( O(	E	) )
Matrice de Adiacență	( O(	V	^2) )
Lista de Adiacență	( O(	V	+

---

8. Concluzie

• Lista arcelor este o metodă simplă și eficientă pentru reprezentarea grafurilor sparse.
• Este ideală pentru algoritmi care necesită procesarea arcelor individuale (ex.: Kruskal).
• Pentru grafuri dense, alte metode (ex.: matricea de adiacență) sunt mai eficiente.