Metode de Reprezentare a Grafurilor: Algoritmul lui Prim 34

---

1. Ce este Algoritmul lui Prim?

Algoritmul Prim este un algoritm utilizat pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat neorientat conectat. Un arbore de acoperire minim este un subgraf care conectează toate nodurile cu costul total minim al muchiilor.

---

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

Algoritmul funcționează pe baza unui proces iterativ:

1. Se pornește cu un nod inițial arbitrar și se adaugă în arbore.
2. La fiecare pas, se alege muchia cu greutatea minimă care conectează un nod din arborele curent la un nod care nu este încă în arbore.
3. Se repetă procesul până când toate nodurile sunt incluse în arbore.

---

4. Complexitate

• Timp: O(E⋅log⁡(V))O(E \cdot \log(V))O(E⋅log(V)), utilizând un Min-Heap (coadă cu priorități).
• Spațiu: O(V+E)O(V + E)O(V+E), pentru stocarea grafului și a structurii de date auxiliare.

---

5. Exemple

Graf Ponderat

Graful:

1 –(2)– 2

|         |

(3)     (1)

|         |

3 –(4)– 4

• Lista de adiacență (reprezentarea grafului):

1: (2, 2), (3, 3)

2: (1, 2), (4, 1)

3: (1, 3), (4, 4)

4: (2, 1), (3, 4)

---

6. Implementare în C++

---

1. Implementare cu Lista de Adiacență și Heap

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

// Structură pentru perechile nod – greutate

typedef pair<int, int> NodGreutate;

void prim(int n, vector<NodGreutate> graful[], int sursa) {

    // Vector pentru distanțe (costurile pentru includerea nodurilor)

    vector<int> cost(n, INT_MAX);

    // Vector pentru a marca nodurile incluse în MST

    vector<bool> inclus(n, false);

    // Vector pentru a reține părinții nodurilor în arbore

    vector<int> parinte(n, -1);

    // Coada cu priorități (min-heap)

    priority_queue<NodGreutate, vector<NodGreutate>, greater<NodGreutate>> minHeap;

    // Inițializarea pentru nodul sursă

    cost[sursa] = 0;

    minHeap.push({0, sursa}); // (cost, nod)

    while (!minHeap.empty()) {

        int nodCurent = minHeap.top().second;

        minHeap.pop();

        // Marcare nod ca inclus în MST

        inclus[nodCurent] = true;

        // Procesăm vecinii nodului curent

        for (auto vecin : graful[nodCurent]) {

            int nodVecin = vecin.first;

            int greutateMuchie = vecin.second;

            // Relaxare: Actualizăm costul dacă găsim o muchie mai ieftină

            if (!inclus[nodVecin] && greutateMuchie < cost[nodVecin]) {

                cost[nodVecin] = greutateMuchie;

                parinte[nodVecin] = nodCurent;

                minHeap.push({cost[nodVecin], nodVecin});

            }

        }

    }

    // Afișăm muchiile din arborele de acoperire minim

    cout << „Muchiile din arborele de acoperire minim:\n”;

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

        if (parinte[i] != -1) {

            cout << parinte[i] + 1 << ” – ” << i + 1 << ” (cost: ” << cost[i] << „)\n”;

        }

    }

}

int main() {

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

    vector<NodGreutate> graful[4];

    // Adăugare muchii

    graful[0].push_back({1, 2}); // 1 – 2, cost 2

    graful[0].push_back({2, 3}); // 1 – 3, cost 3

    graful[1].push_back({0, 2}); // 2 – 1, cost 2

    graful[1].push_back({3, 1}); // 2 – 4, cost 1

    graful[2].push_back({0, 3}); // 3 – 1, cost 3

    graful[2].push_back({3, 4}); // 3 – 4, cost 4

    graful[3].push_back({1, 1}); // 4 – 2, cost 1

    graful[3].push_back({2, 4}); // 4 – 3, cost 4

    int sursa = 0; // Nodul sursă (1)

    prim(n, graful, sursa);

    return 0;

}

---

7. Explicația Codului

1. Lista de adiacență: Reprezintă graful ca o listă de vecini cu greutățile asociate.
2. Relaxare: Pentru fiecare vecin, actualizăm costul dacă găsim o muchie mai ieftină.
3. Coada cu priorități: Asigură procesarea nodurilor în ordine crescătoare a costurilor.

---

8. Aplicații ale Algoritmului lui Prim

1. Rețele de calculatoare:
   Construcția rețelelor cu cost minim între noduri.
2. Planificarea rutelor:
   Optimizarea drumurilor între orașe pentru a minimiza costurile.
3. Proiectarea circuitelor:
   Găsirea conexiunilor optime între componentele unui circuit.
4. Design de infrastructură:
   Construirea rețelelor de transport sau electricitate.

---

9. Concluzie

Algoritmul lui Prim este o soluție eficientă pentru problemele de optimizare în grafuri ponderate. Prin utilizarea unui Min-Heap, acesta asigură performanțe bune chiar și pentru grafuri mari, fiind ideal pentru aplicații practice în rețele și infrastructură.