minimum spanning tree tutorial
Αυτό το σεμινάριο C ++ εξηγεί τι είναι ένα ελάχιστο δέντρο έκτασης (MST) μαζί με τους αλγόριθμους Prim και Kruskal για να βρείτε το MST σε ένα γράφημα και τις εφαρμογές του:
Ένα Spanning tree μπορεί να οριστεί ως ένα υποσύνολο ενός γραφήματος, το οποίο αποτελείται από όλες τις κορυφές που καλύπτουν τις ελάχιστες δυνατές ακμές και δεν έχει κύκλο. Δεν είναι δυνατή η αποσύνδεση του εκτεταμένου δέντρου.
Κάθε συνδεδεμένο και μη κατευθυνόμενο γράφημα έχει τουλάχιστον ένα δέντρο που εκτείνεται. Ένα αποσυνδεδεμένο γράφημα δεν έχει ένα εκτεταμένο δέντρο, καθώς δεν είναι δυνατή η συμπερίληψη όλων των κορυφών.
=> Δείτε εδώ για να εξερευνήσετε τη λίστα με τα πλήρη σεμινάρια C ++.
Τι θα μάθετε:
Δέντρο που εκτείνεται σε C ++
Εξετάστε το ακόλουθο συνδεδεμένο γράφημα.
Όπως φαίνεται παραπάνω, για το δεδομένο συνδεδεμένο γράφημα που περιέχει 3 κορυφές, έχουμε τρία δέντρα. Γενικά, εάν N είναι ο αριθμός των κόμβων σε ένα γράφημα, τότε ένα πλήρες συνδεδεμένο γράφημα έχει το μέγιστο NΝ-2αριθμός δέντρων που εκτείνονται. Έτσι, στο παραπάνω γράφημα N = 3, επομένως, έχει 3(3-2)= 3 δέντρα.
Μερικές από τις ιδιότητες του δέντρου που εκτείνονται αναφέρονται παρακάτω:
- Ένα συνδεδεμένο γράφημα μπορεί να έχει περισσότερα από ένα δέντρα.
- Όλα τα δέντρα που εκτείνονται σε ένα γράφημα έχουν τον ίδιο αριθμό κόμβων και άκρων.
- Εάν αφαιρέσουμε μια άκρη από το δέντρο που εκτείνεται, τότε θα γίνει ελάχιστα συνδεδεμένος και θα αποσυνδέσει το γράφημα.
- Από την άλλη πλευρά, η προσθήκη μιας άκρης στο δέντρο που εκτείνεται θα το κάνει μέγιστα ακυκλικό δημιουργώντας έτσι έναν βρόχο.
- Ένα δέντρο που εκτείνεται δεν έχει βρόχο ή κύκλο.
Τι είναι ένα ελάχιστο δέντρο έκτασης (MST)
Ένα ελάχιστο δέντρο έκτασης είναι εκείνο που περιέχει το μικρότερο βάρος μεταξύ όλων των άλλων δέντρων έκτασης ενός συνδεδεμένου σταθμισμένου γραφήματος. Μπορεί να υπάρχουν περισσότερα από ένα ελάχιστα δέντρα για ένα γράφημα.
Υπάρχουν δύο πιο δημοφιλείς αλγόριθμοι που χρησιμοποιούνται για την εύρεση του ελάχιστου δέντρου έκτασης σε ένα γράφημα.
Περιλαμβάνουν:
- Ο αλγόριθμος του Kruskal
- Ο αλγόριθμος του Prim
Ας συζητήσουμε και τους δύο αυτούς αλγόριθμους!
Αλγόριθμος του Kruskal
Ο αλγόριθμος του Kruskal είναι ένας αλγόριθμος για την εύρεση του MST σε ένα συνδεδεμένο γράφημα.
Ο αλγόριθμος του Kruskal βρίσκει ένα υποσύνολο ενός γραφήματος G έτσι ώστε:
- Σχηματίζει ένα δέντρο με κάθε κορυφή σε αυτό.
- Το άθροισμα των βαρών είναι το ελάχιστο μεταξύ όλων των δέντρων που μπορούν να σχηματιστούν από αυτό το γράφημα.
Η ακολουθία των βημάτων για τον αλγόριθμο του Kruskal δίνεται ως εξής:
- Πρώτα ταξινομήστε όλες τις άκρες από το χαμηλότερο βάρος στο υψηλότερο.
- Εκμεταλλευτείτε το χαμηλότερο βάρος και προσθέστε το στο δέντρο που εκτείνεται. Εάν δημιουργηθεί ο κύκλος, απορρίψτε το άκρο.
- Συνεχίστε να προσθέτετε άκρα όπως στο βήμα 1 έως ότου ληφθούν υπόψη όλες οι κορυφές.
Ψευδοκώδικας για τον αλγόριθμο του Kruskal
Παρακάτω δίνεται ο ψευδοκώδικας για τον Αλγόριθμο του Kruskal
Τώρα ας δούμε την απεικόνιση του αλγορίθμου του Kruskal.
Τώρα επιλέγουμε το άκρο με το μικρότερο βάρος που είναι 2-4.
Στη συνέχεια, επιλέξτε το επόμενο μικρότερο άκρο 2-3.
Στη συνέχεια, επιλέγουμε το επόμενο άκρο με το μικρότερο άκρο και αυτό δεν δημιουργεί κύκλο, δηλαδή 0-3
όνομα του λειτουργικού συστήματος στον υπολογιστή
Το επόμενο βήμα είναι να επιλέξετε το συντομότερο άκρο έτσι ώστε να μην σχηματίζει κύκλο. Αυτό είναι 0-1.
Όπως μπορούμε να δούμε, έχουμε καλύψει όλες τις κορυφές και έχουμε ένα δέντρο με ελάχιστο κόστος εδώ.
Στη συνέχεια, θα εφαρμόσουμε τον Αλγόριθμο του Kruskal χρησιμοποιώντας το C ++.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i Παραγωγή:
Το ελάχιστο δέντρο έκτασης (MST) σύμφωνα με τον αλγόριθμο του Kruskal:
Άκρη: Βάρος
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Σημειώστε ότι χρησιμοποιήσαμε το ίδιο παράδειγμα γραφήματος στο πρόγραμμα με αυτό που χρησιμοποιήσαμε στην απεικόνιση του αλγόριθμου Kruskal παραπάνω. Σε αυτήν την εφαρμογή χρησιμοποιούμε δύο διανύσματα. ένα για να αποθηκεύσετε το γράφημα και ένα άλλο για να αποθηκεύσετε το ελάχιστο δέντρο έκτασης. Βρίσκουμε αναδρομικά τις άκρες με το μικρότερο βάρος και τις προσθέτουμε στο φορέα MST μέχρι να καλυφθούν όλες οι κορυφές.
Αλγόριθμος Prim
Ο αλγόριθμος Prim είναι ένας άλλος αλγόριθμος που βρίσκει το ελάχιστο που καλύπτει το δέντρο ενός γραφήματος. Σε αντίθεση με τον αλγόριθμο Kruskal που ξεκινά με άκρα γραφήματος, ο αλγόριθμος Prim ξεκινά με μια κορυφή. Ξεκινάμε με μία κορυφή και συνεχίζουμε να προσθέτουμε άκρα με το μικρότερο βάρος μέχρι να καλυφθούν όλες οι κορυφές.
Η ακολουθία των βημάτων για τον Αλγόριθμο Prim είναι η εξής:
- Επιλέξτε μια τυχαία κορυφή ως αρχική κορυφή και αρχικοποιήστε ένα ελάχιστο δέντρο έκτασης.
- Βρείτε τις άκρες που συνδέονται με άλλες κορυφές. Βρείτε την άκρη με ελάχιστο βάρος και προσθέστε το στο δέντρο που εκτείνεται.
- Επαναλάβετε το βήμα 2 έως ότου επιτευχθεί το δέντρο που εκτείνεται.
Ψευδοκώδικας για τον αλγόριθμο του Prim
Τώρα ας δούμε μια εικόνα για τον αλγόριθμο του Prim.
Γι 'αυτό, χρησιμοποιούμε το ίδιο παράδειγμα γραφήματος που χρησιμοποιήσαμε στον αλγόριθμο Εικονογράφηση του Kruskal.
Ας επιλέξουμε τον κόμβο 2 ως την τυχαία κορυφή.
Στη συνέχεια, επιλέγουμε το άκρο με το μικρότερο βάρος από το 2. Επιλέγουμε το άκρο 2-4.
Στη συνέχεια, επιλέγουμε μια άλλη κορυφή που δεν βρίσκεται ακόμα στο δέντρο έκτασης. Επιλέγουμε το άκρο 2-3.
Τώρα ας επιλέξουμε ένα άκρο με λιγότερο βάρος από τις παραπάνω κορυφές. Έχουμε το άκρο 3-0 που έχει το μικρότερο βάρος.
Στη συνέχεια, επιλέγουμε ένα άκρο με το μικρότερο βάρος από την κορυφή 0. Αυτό είναι το άκρο 0-1.
Από το παραπάνω σχήμα, βλέπουμε ότι έχουμε πλέον καλύψει όλες τις κορυφές του γραφήματος και έχουμε αποκτήσει ένα πλήρες δέντρο με ελάχιστο κόστος.
Τώρα ας εφαρμόσουμε τον αλγόριθμο Prim στο C ++.
Σημειώστε ότι και σε αυτό το πρόγραμμα, χρησιμοποιήσαμε το παραπάνω παράδειγμα γραφήματος ως είσοδο, ώστε να μπορούμε να συγκρίνουμε την έξοδο που δίνεται από το πρόγραμμα μαζί με την εικόνα.
Το πρόγραμμα δίνεται παρακάτω:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } Παραγωγή:
Το ελάχιστο δέντρο έκτασης σύμφωνα με τον αλγόριθμο του Prim:
Άκρη: Βάρος
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Εφαρμογές του Spanning Tree
Ορισμένες από τις εφαρμογές των Ελάχιστων Δέντρων είναι οι εξής:
# 1) Ρύθμιση δικτύου επικοινωνιών: Όταν θέλουμε να δημιουργήσουμε ένα δίκτυο επικοινωνίας χρησιμοποιώντας συνδέσμους επικοινωνίας, τότε το κόστος δημιουργίας συνδέσμων επικοινωνίας μεταξύ δύο σημείων καθορίζεται καλύτερα χρησιμοποιώντας ένα MST.
# 2) Ανάλυση συμπλέγματος: Μπορεί να χρησιμοποιηθεί για την επίλυση του προβλήματος συμπλέγματος Κ βρίσκοντας ένα ελάχιστο δέντρο έκτασης και διαγράφοντας το πιο ακριβό άκρο του k-1.
# 3) Διαμόρφωση οδικών / σιδηροδρομικών δικτύων: Όταν δημιουργούμε διάφορα οδικά ή σιδηροδρομικά δίκτυα μεταξύ ή εντός πόλεων, το κόστος του έργου είναι ένας πολύ σημαντικός παράγοντας. Μπορούμε να βρούμε την καλύτερη διαδρομή με ελάχιστο κόστος χρησιμοποιώντας ελάχιστα δέντρα.
# 4) Σχεδιασμός εγκαταστάσεων στέγασης: Εγκαταστάσεις όπως ηλεκτρισμός, νερό, λύματα κ.λπ. που παρέχονται σε ορισμένα σπίτια πρέπει επίσης να είναι στο βέλτιστο κόστος και αυτό γίνεται με MST.
# 5) Επίλυση του προβλήματος του Traveling Salesman: Μπορούμε να χρησιμοποιήσουμε ένα MST για να λύσουμε το πρόβλημα του ταξιδιώτη πωλητή που απαιτεί να επισκεφτείτε κάθε σημείο τουλάχιστον μία φορά.
συμπέρασμα
Το ελάχιστο δέντρο έκτασης είναι το υποσύνολο του γραφήματος g και αυτό το υποσύνολο έχει όλες τις κορυφές του γραφήματος και το συνολικό κόστος των άκρων που συνδέουν τις κορυφές είναι ελάχιστο.
Συζητήσαμε δύο αλγόριθμους, δηλαδή Kruskal και Prim, για να βρούμε το ελάχιστο δέντρο από το γράφημα. Οι Εφαρμογές του δέντρου που εκτείνονται επεξηγήθηκαν επίσης εδώ σε αυτό το σεμινάριο.
=> Δείτε τα καλύτερα εκπαιδευτικά σεμινάρια C ++ εδώ.
Συνιστώμενη ανάγνωση
- Εκμάθηση Java Reflection με παραδείγματα
- B Δομή Δέντρων και Δ + Δέντρων Δεδομένων σε C ++
- Εκμάθηση Python DateTime με παραδείγματα
- Tutorial Bugzilla: Εργαλείο Διαχείρισης Ατελειών
- Δομή Δυαδικών Δέντρων Στο C ++
- 20+ MongoDB Tutorial για αρχάριους: Δωρεάν μαθήματα MongoDB
- MongoDB Sharding Tutorial με Παράδειγμα
- Οδηγός δημιουργίας βάσης δεδομένων MongoDB
