Structuri de Date Arborescente Implementate Dinamic – Arbore Parțial de Cost Minim 13
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore parțial de cost minim (Minimum Spanning Tree – MST).
- Să învețe algoritmii clasici pentru determinarea MST: Kruskal și Prim.
- Să implementeze MST folosind structuri dinamice.
2. Ce este un arbore parțial de cost minim?
- Definiție:
Un arbore parțial de cost minim este un subgraf al unui graf ponderat, conex și neorientat, care:- Include toate nodurile grafului.
- Are cel mai mic cost total posibil (suma ponderilor muchiilor).
- Este un arbore (nu conține cicluri).
- Proprietăți:
- Un graf poate avea mai mulți MST cu același cost.
- Numărul muchiilor dintr-un MST este întotdeauna V−1V – 1V−1, unde VVV este numărul de noduri.
3. Aplicații practice ale MST
- Construcția rețelelor (electricitate, drumuri, internet).
- Compresia datelor (algoritmul lui Huffman).
- Optimizarea resurselor într-o organizație.
4. Algoritmi clasici pentru MST
- Algoritmul lui Kruskal:
- Ideea principală: Selectează muchiile grafului în ordine crescătoare a costurilor, asigurându-se că nu se formează cicluri.
- Pași:
- Sortează muchiile grafului după cost.
- Adaugă fiecare muchie (în ordine) dacă nu formează un ciclu.
- Algoritmul lui Prim:
- Ideea principală: Construiește MST pornind de la un nod inițial și adăugând muchii de cost minim care conectează noduri noi.
- Pași:
- Alege un nod de pornire.
- Selectează muchia de cost minim care leagă un nod inclus cu un nod neinclus.
5. Implementarea algoritmului lui Kruskal
Structura pentru reprezentarea grafului
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Muchie {
int sursa, destinatie, cost;
};
// Comparator pentru sortarea muchiilor după cost
bool comparaMuchii(const Muchie& a, const Muchie& b) {
return a.cost < b.cost;
}
Reprezentarea Uniunii și Găsirii (Union-Find)
struct DisjointSet {
vector<int> parinte, rang;
DisjointSet(int n) {
parinte.resize(n);
rang.resize(n, 0);
for (int i = 0; i < n; i++) {
parinte[i] = i;
}
}
int gaseste(int u) {
if (u != parinte[u]) {
parinte[u] = gaseste(parinte[u]);
}
return parinte[u];
}
void uneste(int u, int v) {
u = gaseste(u);
v = gaseste(v);
if (u != v) {
if (rang[u] < rang[v]) {
parinte[u] = v;
} else if (rang[u] > rang[v]) {
parinte[v] = u;
} else {
parinte[v] = u;
rang[u]++;
}
}
}
};
Algoritmul lui Kruskal
int kruskalMST(vector<Muchie>& muchii, int numarNoduri) {
sort(muchii.begin(), muchii.end(), comparaMuchii); // Sortează muchiile după cost
DisjointSet ds(numarNoduri);
int costTotal = 0;
vector<Muchie> rezultat;
for (const auto& muchie : muchii) {
if (ds.gaseste(muchie.sursa) != ds.gaseste(muchie.destinatie)) {
rezultat.push_back(muchie);
costTotal += muchie.cost;
ds.uneste(muchie.sursa, muchie.destinatie);
}
}
cout << „Muchiile din MST:\n”;
for (const auto& muchie : rezultat) {
cout << muchie.sursa << ” – ” << muchie.destinatie << ” : ” << muchie.cost << endl;
}
return costTotal;
}
Exemplu de utilizare
int main() {
int numarNoduri = 4;
vector<Muchie> muchii = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
int costTotal = kruskalMST(muchii, numarNoduri);
cout << „Costul total al MST: ” << costTotal << endl;
return 0;
}
6. Implementarea algoritmului lui Prim
Structura pentru reprezentarea grafului
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> Pereche; // cost, nod
Algoritmul lui Prim
int primMST(vector<vector<Pereche>>& graf, int numarNoduri) {
priority_queue<Pereche, vector<Pereche>, greater<Pereche>> pq;
vector<bool> inclus(numarNoduri, false);
int costTotal = 0;
pq.push({0, 0}); // Pornim de la nodul 0 cu cost 0
while (!pq.empty()) {
int cost = pq.top().first;
int nod = pq.top().second;
pq.pop();
if (inclus[nod]) continue;
inclus[nod] = true;
costTotal += cost;
for (const auto& vecin : graf[nod]) {
if (!inclus[vecin.second]) {
pq.push(vecin);
}
}
}
return costTotal;
}
Exemplu de utilizare
int main() {
int numarNoduri = 5;
vector<vector<Pereche>> graf(numarNoduri);
graf[0].push_back({2, 1});
graf[0].push_back({3, 3});
graf[1].push_back({2, 0});
graf[1].push_back({5, 2});
graf[1].push_back({8, 3});
graf[2].push_back({5, 1});
graf[2].push_back({7, 3});
graf[3].push_back({3, 0});
graf[3].push_back({8, 1});
graf[3].push_back({7, 2});
int costTotal = primMST(graf, numarNoduri);
cout << „Costul total al MST: ” << costTotal << endl;
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care verifică dacă un graf are mai mulți arbori parțiali de cost minim.
- Adăugați opțiuni de a construi un graf utilizând matricea de adiacență și lista de adiacență.
- Implementați o aplicație care compară costurile MST folosind algoritmii lui Kruskal și Prim.
8. Scheme logice
- Algoritmul lui Kruskal:
- Sortează muchiile -> Verifică ciclurile -> Adaugă muchiile valide în MST.
- Algoritmul lui Prim:
- Selectează un nod inițial -> Găsește muchia de cost minim -> Adaugă nodul conectat.
9. Concluzie
- Arborii parțiali de cost minim sunt esențiali pentru optimizarea resurselor în grafuri.
- Algoritmii lui Kruskal și Prim sunt eficienți pentru rezolvarea MST.
- Practica ajută la înțelegerea algoritmilor și la aplicarea lor în situații reale.