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
- Sortare: Se sortează toate muchiile grafului în funcție de greutatea lor.
- Adăugare: Se adaugă pe rând cele mai ușoare muchii la arbore, cu condiția să nu formeze un ciclu.
- 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
- 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.
- 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
- Rețele de calculatoare:
Construcția rețelelor cu cost minim între noduri. - Proiectarea circuitelor:
Găsirea conexiunilor optime între componente. - Rețele de transport:
Optimizarea drumurilor între orașe. - 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.