Ένα ελάχιστο δέντρο κάλυψης (MST) συνδέει όλες τις κορυφές ενός σταθμισμένου, συνδεδεμένου γραφήματος με ελάχιστο συνολικό βάρος ακμών και χωρίς κύκλους. Ο Kruskal και ο Prim είναι δύο κλασικοί άπληστοι αλγόριθμοι.
Ταξινομήστε όλες τις ακμές κατά βάρος· προσθέστε την φθηνότερη ακμή που δεν σχηματίζει κύκλο.
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
Ξεκινήστε από οποιαδήποτε κορυφή· επαναλαμβανόμενα προσθέστε την φθηνότερη ακμή που εγκαταλείπει το τρέχον δέντρο.
| | Kruskal | Prim | |---|--------|------|| | Προσέγγιση | ταξινόμηση ακμών + union-find | ανάπτυξη από κόμβο + heap | | Χρόνος | O(E log E) | O(E log V) | | Καλύτερο για | αραιά γραφήματα | πυκνά γραφήματα |
Χρησιμοποιήστε το MST για σχεδιασμό δικτύου — τοποθέτηση καλωδίων, σωλήνων νερού, ομαδοποίηση. Και τα δύο είναι άπληστα και αποδεικτικά βέλτιστα εδώ. Ο Kruskal χρειάζεται union-find για να αποφύγει αποτελεσματικά κύκλους.
Το MST ελαχιστοποιεί το κόστος σύνδεσης όλων — άμεσα εφαρμόσιμο στη δομή και το σχεδιασμό δικτύου.
Είναι μια καθαρή περίπτωση όπου ο άπληστος αλγόριθμος είναι αποδεικτικά βέλτιστος, ενισχύοντας τη λογική της άπληστης επιλογής.
Ο Kruskal επίσης παρουσιάζει union-find, μια δομή με ευρύ αλγοριθμικό εύρος.
Μια βιβλιοθήκη ερωτήσεων συνέντευξης IT με αναλυτικές απαντήσεις — από Junior έως Senior.
Δωρεά