Metode de Reprezentare a Grafurilor: Algoritmul lui Kruskal 35

---

1. Ce este Algoritmul lui Kruskal?

Algoritmul Kruskal este o metodă pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat, neorientat. Se bazează pe alegerea iterativă a muchiilor cu cea mai mică greutate, asigurându-se că nu se formează cicluri.

---

2. Obiectiv

• Construcția unui arbore de acoperire minim TTT, unde suma greutăților muchiilor este minimă: min⁡∑(u,v)∈Tw(u,v)\min \sum_{(u, v) \in T} w(u, v)min(u,v)∈T∑​w(u,v)

---

3. Ideea Algoritmului

1. Sortare: Se sortează toate muchiile grafului în funcție de greutatea lor.
2. Adăugare: Se adaugă pe rând cele mai ușoare muchii la arbore, cu condiția să nu formeze un ciclu.
3. Oprire: Algoritmul se oprește când arborele de acoperire conține ∣V∣−1|V| – 1∣V∣−1 muchii (unde ∣V∣|V|∣V∣ este numărul de noduri).

Pentru a detecta ciclurile eficient, se folosește o structură Union-Find (Disjoint Set Union – DSU).

---

4. Complexitate

• Timp: O(E⋅log⁡(E))O(E \cdot \log(E))O(E⋅log(E)), unde EEE este numărul de muchii.
  • Sortarea muchiilor: O(E⋅log⁡(E))O(E \cdot \log(E))O(E⋅log(E)).
  • Operații Union-Find: O(E⋅log⁡(V))O(E \cdot \log(V))O(E⋅log(V)).
• Spațiu: O(V+E)O(V + E)O(V+E), pentru stocarea grafului și a structurii DSU.

---

5. Exemplu

Graf Ponderat

Graful:

1 –(1)– 2

|         |

(4)     (3)

|         |

3 –(2)– 4

• Lista Muchiilor:

(1, 2, 1)

(3, 4, 2)

(2, 4, 3)

(1, 3, 4)

---

6. Implementare în C++

---

1. Structura Union-Find

class DisjointSetUnion {

public:

    vector<int> parinte, rang;

    DisjointSetUnion(int n) {

        parinte.resize(n);

        rang.resize(n, 0);

        for (int i = 0; i < n; i++) {

            parinte[i] = i; // Fiecare nod este inițial propriul său părinte

        }

    }

    int gaseste(int nod) {

        if (parinte[nod] != nod) {

            parinte[nod] = gaseste(parinte[nod]); // Compresia drumului

        }

        return parinte[nod];

    }

    void uneste(int nod1, int nod2) {

        int radacina1 = gaseste(nod1);

        int radacina2 = gaseste(nod2);

        if (radacina1 != radacina2) {

            if (rang[radacina1] < rang[radacina2]) {

                parinte[radacina1] = radacina2;

            } else if (rang[radacina1] > rang[radacina2]) {

                parinte[radacina2] = radacina1;

            } else {

                parinte[radacina2] = radacina1;

                rang[radacina1]++;

            }

        }

    }

};

---

2. Algoritmul lui Kruskal

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Structură pentru muchii

struct Muchie {

    int u, v, greutate;

    bool operator<(const Muchie& alt) const {

        return greutate < alt.greutate;

    }

};

void kruskal(int n, vector<Muchie>& muchii) {

    // Sortăm muchiile după greutate

    sort(muchii.begin(), muchii.end());

    // Structura Union-Find

    DisjointSetUnion dsu(n);

    vector<Muchie> arbore;

    int costTotal = 0;

    for (const auto& muchie : muchii) {

        if (dsu.gaseste(muchie.u) != dsu.gaseste(muchie.v)) {

            dsu.uneste(muchie.u, muchie.v);

            arbore.push_back(muchie);

            costTotal += muchie.greutate;

        }

    }

    // Afișăm rezultatul

    cout << „Arborele de acoperire minim:\n”;

    for (const auto& muchie : arbore) {

        cout << muchie.u + 1 << ” – ” << muchie.v + 1 << ” (cost: ” << muchie.greutate << „)\n”;

    }

    cout << „Cost total: ” << costTotal << endl;

}

int main() {

    int n = 4; // Numărul de noduri

    vector<Muchie> muchii = {

        {0, 1, 1}, // 1 – 2, cost 1

        {2, 3, 2}, // 3 – 4, cost 2

        {1, 3, 3}, // 2 – 4, cost 3

        {0, 2, 4}  // 1 – 3, cost 4

    };

    kruskal(n, muchii);

    return 0;

}

---

7. Explicația Codului

1. Structura Union-Find:
   • Se utilizează pentru detectarea ciclurilor în timp eficient.
   • Funcția gaseste determină reprezentantul (radacina) unui nod.
   • Funcția uneste unește două componente conexe.
2. Algoritmul:
   • Sortează toate muchiile în ordine crescătoare a greutății.
   • Adaugă muchiile în arbore dacă nu formează cicluri, utilizând Union-Find.

---

8. Aplicații ale Algoritmului lui Kruskal

1. Rețele de calculatoare:
   Construcția rețelelor cu cost minim între noduri.
2. Proiectarea circuitelor:
   Găsirea conexiunilor optime între componente.
3. Rețele de transport:
   Optimizarea drumurilor între orașe.
4. Design de infrastructură:
   Construirea rețelelor de apă, gaz, electricitate sau telecomunicații.

---

9. Concluzie

Algoritmul lui Kruskal este o soluție simplă și eficientă pentru problemele de arbore de acoperire minim. Fiind bazat pe sortare și Union-Find, este ideal pentru grafuri mari, sparse sau dense.