Πώς δημιουργούν ο Kruskal και ο Prim ένα ελάχιστο δέντρο κάλυψης;

Question

Accepted Answer

Ένα **ελάχιστο δέντρο κάλυψης (MST)** συνδέει όλες τις κορυφές ενός σταθμισμένου, συνδεδεμένου γραφήματος με **ελάχιστο συνολικό βάρος ακμών** και χωρίς κύκλους. Ο **Kruskal** και ο **Prim** είναι δύο κλασικοί άπληστοι αλγόριθμοι.

## Kruskal (ταξινόμηση ακμών, union-find)

Ταξινομήστε όλες τις ακμές κατά βάρος· προσθέστε την φθηνότερη ακμή που δεν σχηματίζει κύκλο.

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (ανάπτυξη δέντρου με min-heap)

Ξεκινήστε από οποιαδήποτε κορυφή· επαναλαμβανόμενα προσθέστε την φθηνότερη ακμή που εγκαταλείπει το τρέχον δέντρο.

## Σύγκριση

| | Kruskal | Prim |
|---|--------|------||
| Προσέγγιση | ταξινόμηση ακμών + union-find | ανάπτυξη από κόμβο + heap |
| Χρόνος | O(E log E) | O(E log V) |
| Καλύτερο για | αραιά γραφήματα | πυκνά γραφήματα |

## Πότε να χρησιμοποιήσετε / Παγίδες

Χρησιμοποιήστε το MST για **σχεδιασμό δικτύου** — τοποθέτηση καλωδίων, σωλήνων νερού, ομαδοποίηση. Και τα δύο είναι άπληστα και αποδεικτικά βέλτιστα εδώ. Ο Kruskal χρειάζεται union-find για να αποφύγει αποτελεσματικά κύκλους.

## Γιατί έχει σημασία

Το MST ελαχιστοποιεί το κόστος σύνδεσης όλων — άμεσα εφαρμόσιμο στη δομή και το σχεδιασμό δικτύου.

Είναι μια καθαρή περίπτωση όπου ο άπληστος αλγόριθμος είναι αποδεικτικά βέλτιστος, ενισχύοντας τη λογική της άπληστης επιλογής.

Ο Kruskal επίσης παρουσιάζει union-find, μια δομή με ευρύ αλγοριθμικό εύρος.