java graph tutorial how implement graph data structure
Αυτό το περιεκτικό σεμινάριο γραφημάτων Java εξηγεί λεπτομερώς τη δομή δεδομένων γραφήματος. Περιλαμβάνει τον τρόπο δημιουργίας, εφαρμογής, αναπαράστασης και διέλευσης γραφημάτων στην Java:
Μια δομή δεδομένων γραφήματος αντιπροσωπεύει κυρίως ένα δίκτυο που συνδέει διάφορα σημεία. Αυτά τα σημεία ονομάζονται κορυφές και οι σύνδεσμοι που συνδέουν αυτές τις κορυφές ονομάζονται «άκρες». Έτσι, ένα γράφημα g ορίζεται ως ένα σύνολο κορυφών V και ακμών Ε που συνδέουν αυτές τις κορυφές.
Τα γραφήματα χρησιμοποιούνται ως επί το πλείστον για να αντιπροσωπεύουν διάφορα δίκτυα όπως δίκτυα υπολογιστών, κοινωνικά δίκτυα κ.λπ. Μπορούν επίσης να χρησιμοποιηθούν για να αντιπροσωπεύουν διάφορες εξαρτήσεις σε λογισμικό ή αρχιτεκτονικές. Αυτά τα γραφήματα εξάρτησης είναι πολύ χρήσιμα για την ανάλυση του λογισμικού και επίσης κατά καιρούς το εντοπισμό σφαλμάτων.
=> Ελέγξτε ΟΛΑ τα Εκπαιδευτικά Java εδώ.
Τι θα μάθετε:
- Δομή δεδομένων γραφήματος Java
- Πώς να δημιουργήσετε ένα γράφημα;
- Υλοποίηση γραφήματος σε Java
- Βιβλιοθήκη γραφήματος Java
- συμπέρασμα
Δομή δεδομένων γραφήματος Java
Δίνεται παρακάτω ένα γράφημα που έχει πέντε κορυφές {A, B, C, D, E} και άκρα που δίνονται από {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Δεδομένου ότι τα άκρα δεν δείχνουν κατεύθυνση, αυτό το γράφημα είναι γνωστό ως «μη κατευθυνόμενο γράφημα».
Εκτός από το μη κατευθυνόμενο γράφημα που φαίνεται παραπάνω, υπάρχουν αρκετές παραλλαγές του γραφήματος στην Java.
Ας συζητήσουμε λεπτομερώς αυτές τις παραλλαγές.
Διαφορετικές παραλλαγές του γραφήματος
Τα παρακάτω είναι μερικές από τις παραλλαγές του γραφήματος.
# 1) Κατευθυνόμενο γράφημα
Ένα κατευθυνόμενο γράφημα ή διάγραμμα είναι μια δομή δεδομένων γραφήματος στην οποία τα άκρα έχουν μια συγκεκριμένη κατεύθυνση. Προέρχονται από μια κορυφή και κορυφώνονται σε μια άλλη κορυφή.
Το παρακάτω διάγραμμα δείχνει το παράδειγμα του κατευθυνόμενου γραφήματος.
Στο παραπάνω διάγραμμα, υπάρχει μια άκρη από την κορυφή Α έως την κορυφή Β. Ωστόσο, σημειώστε ότι το Α έως το Β δεν είναι το ίδιο με το Β στο Α όπως στο μη κατευθυνόμενο γράφημα εκτός εάν υπάρχει ένα άκρο που καθορίζεται από το Β στο Α.
Ένα κατευθυνόμενο γράφημα είναι κυκλικό εάν υπάρχει τουλάχιστον μία διαδρομή που έχει την πρώτη και τελευταία κορυφή ως ίδια. Στο παραπάνω διάγραμμα, μια διαδρομή A-> B-> C-> D-> E-> A σχηματίζει έναν κατευθυνόμενο κύκλο ή κυκλικό γράφημα.
Αντίθετα, ένα κατευθυνόμενο ακυκλικό γράφημα είναι ένα γράφημα στο οποίο δεν υπάρχει κατευθυνόμενος κύκλος, δηλαδή δεν υπάρχει διαδρομή που σχηματίζει κύκλο.
# 2) Σταθμισμένο γράφημα
Σε ένα σταθμισμένο γράφημα, ένα βάροςσχετίζεται με κάθε άκρη του γραφήματος. Το βάρος δείχνει συνήθως την απόσταση μεταξύ των δύο κορυφών. Το παρακάτω διάγραμμα δείχνει το σταθμισμένο γράφημα. Δεδομένου ότι δεν εμφανίζονται οδηγίες, αυτό είναι το μη κατευθυνόμενο γράφημα.
Σημειώστε ότι ένα σταθμισμένο γράφημα μπορεί να κατευθύνεται ή να κατευθύνεται.
Πώς να δημιουργήσετε ένα γράφημα;
Η Java δεν παρέχει πλήρη εφαρμογή της δομής δεδομένων γραφήματος. Ωστόσο, μπορούμε να αναπαραστήσουμε το γράφημα μέσω προγραμματισμού χρησιμοποιώντας τις Συλλογές στην Java. Μπορούμε επίσης να εφαρμόσουμε ένα γράφημα χρησιμοποιώντας δυναμικές συστοιχίες όπως διανύσματα.
διαφορά μεταξύ δοκιμής μαύρου κουτιού και λευκού κουτιού
Συνήθως, εφαρμόζουμε γραφήματα σε Java χρησιμοποιώντας τη συλλογή HashMap. Τα στοιχεία HashMap έχουν τη μορφή ζευγών κλειδιών-τιμών. Μπορούμε να αντιπροσωπεύσουμε τη λίστα γειτνίασης γραφήματος σε ένα HashMap.
Ένας πιο συνηθισμένος τρόπος για να δημιουργήσετε ένα γράφημα είναι με τη χρήση μίας από τις αναπαραστάσεις γραφημάτων όπως πίνακας adjacency ή λίστα adjacency. Στη συνέχεια θα συζητήσουμε αυτές τις παραστάσεις και στη συνέχεια θα εφαρμόσουμε το γράφημα στην Java χρησιμοποιώντας τη λίστα γειτνίασης για την οποία θα χρησιμοποιήσουμε το ArrayList.
Αναπαράσταση γραφήματος στην Ιάβα
Αναπαράσταση γραφήματος σημαίνει την προσέγγιση ή την τεχνική με την οποία τα δεδομένα γραφημάτων αποθηκεύονται στη μνήμη του υπολογιστή.
Έχουμε δύο κύριες αναπαραστάσεις γραφημάτων όπως φαίνεται παρακάτω.
Πίνακας προσαρμογής
Το Adjacency Matrix είναι μια γραμμική αναπαράσταση γραφημάτων. Αυτός ο πίνακας αποθηκεύει τη χαρτογράφηση κορυφών και άκρων του γραφήματος. Στη μήτρα γειτνίασης, οι κορυφές του γραφήματος αντιπροσωπεύουν σειρές και στήλες. Αυτό σημαίνει ότι εάν το γράφημα έχει N κορυφές, τότε ο πίνακας γειτνίασης θα έχει μέγεθος NxN.
Εάν το V είναι ένα σύνολο κορυφών του γραφήματος, τότε η τομή Mijστη λίστα γειτνίασης = 1 σημαίνει ότι υπάρχει ένα άκρο μεταξύ των κορυφών i και j.
Για να κατανοήσουμε καλύτερα αυτήν την ιδέα, ας προετοιμάσουμε ένα Matrix γειτνίασης για ένα μη κατευθυνόμενο γράφημα.
Όπως φαίνεται από το παραπάνω διάγραμμα, βλέπουμε ότι για την κορυφή Α, οι διασταυρώσεις ΑΒ και ΑΕ ρυθμίζονται στο 1 καθώς υπάρχει ένα άκρο από Α έως Β και Α έως Ε. Ομοίως, η διασταύρωση ΒΑ έχει οριστεί σε 1, καθώς αυτό είναι μη κατευθυνόμενο γράφημα και AB = BA. Ομοίως, έχουμε ορίσει όλες τις άλλες διασταυρώσεις για τις οποίες υπάρχει ένα πλεονέκτημα στο 1.
Σε περίπτωση που το γράφημα κατευθύνεται, η τομή Μijθα οριστεί σε 1 μόνο εάν υπάρχει ένα σαφές άκρο που κατευθύνεται από το Vi στο Vj.
Αυτό φαίνεται στην παρακάτω εικόνα.
Όπως μπορούμε να δούμε από το παραπάνω διάγραμμα, υπάρχει μια άκρη από το Α έως το Β. Επομένως, η διασταύρωση ΑΒ έχει οριστεί στο 1, αλλά η διασταύρωση ΒΑ έχει οριστεί στο 0. Αυτό συμβαίνει επειδή δεν υπάρχει ακμή που κατευθύνεται από το Β στο Α.
Εξετάστε τις κορυφές E και D. Βλέπουμε ότι υπάρχουν άκρα από E έως D καθώς και D έως E. Ως εκ τούτου, έχουμε θέσει και τις δύο αυτές διασταυρώσεις στο 1 στο Matrix γειτνίασης.
Τώρα προχωράμε στα σταθμισμένα γραφήματα. Όπως γνωρίζουμε για το σταθμισμένο γράφημα, ένας ακέραιος επίσης γνωστός ως βάρος σχετίζεται με κάθε άκρη. Αντιπροσωπεύουμε αυτό το βάρος στο Matrix γειτνίασης με το άκρο που υπάρχει. Αυτό το βάρος καθορίζεται όποτε υπάρχει άκρη από τη μία κορυφή στην άλλη αντί για «1».
Αυτή η αναπαράσταση φαίνεται παρακάτω.
Λίστα ικανοτήτων
Αντί να αναπαριστάμε ένα γράφημα ως πίνακας γειτνίασης που έχει διαδοχική φύση, μπορούμε επίσης να χρησιμοποιήσουμε συνδεδεμένη αναπαράσταση. Αυτή η συνδεδεμένη παράσταση είναι γνωστή ως λίστα γειτνίασης. Μια λίστα γειτνίασης δεν είναι παρά μια συνδεδεμένη λίστα και κάθε κόμβος στη λίστα αντιπροσωπεύει μια κορυφή.
Η παρουσία ενός άκρου μεταξύ δύο κορυφών υποδηλώνεται από ένα δείκτη από την πρώτη κορυφή προς τη δεύτερη. Αυτή η λίστα γειτνίασης διατηρείται για κάθε κορυφή στο γράφημα.
Όταν έχουμε διασχίσει όλους τους γειτονικούς κόμβους για έναν συγκεκριμένο κόμβο, αποθηκεύουμε το NULL στο επόμενο πεδίο δείκτη του τελευταίου κόμβου της λίστας γειτνίασης.
Τώρα θα χρησιμοποιήσουμε τα παραπάνω γραφήματα που χρησιμοποιήσαμε για να αντιπροσωπεύσουμε τη μήτρα γειτνίασης για να δείξουμε τη λίστα γειτνίασης.
Το παραπάνω σχήμα δείχνει τη λίστα γειτνίασης με το μη κατευθυνόμενο γράφημα. Βλέπουμε ότι κάθε κορυφή ή κόμβος έχει τη λίστα γειτνίασης.
Στην περίπτωση του μη κατευθυνόμενου γραφήματος, τα συνολικά μήκη των λιστών γειτνίασης είναι συνήθως διπλάσιο από τον αριθμό των άκρων. Στο παραπάνω γράφημα, ο συνολικός αριθμός των άκρων είναι 6 και το σύνολο ή το άθροισμα του μήκους όλης της λίστας γειτνίασης είναι 12.
Τώρα ας προετοιμάσουμε μια λίστα γειτνίασης με το κατευθυνόμενο γράφημα.
Όπως φαίνεται από το παραπάνω σχήμα, στο κατευθυνόμενο γράφημα το συνολικό μήκος των λιστών γειτνίασης του γραφήματος είναι ίσο με τον αριθμό των άκρων του γραφήματος. Στο παραπάνω γράφημα, υπάρχουν 9 άκρα και άθροισμα των μηκών λιστών γειτνίασης για αυτό το γράφημα = 9.
Τώρα ας εξετάσουμε το ακόλουθο σταθμισμένο γράφημα. Σημειώστε ότι κάθε άκρη του σταθμισμένου γραφήματος σχετίζεται με ένα βάρος. Έτσι, όταν αντιπροσωπεύουμε αυτό το γράφημα με τη λίστα γειτνίασης, πρέπει να προσθέσουμε ένα νέο πεδίο σε κάθε κόμβο λίστας που θα υποδηλώνει το βάρος του άκρου.
Η λίστα γειτνίασης με το σταθμισμένο γράφημα φαίνεται παρακάτω.
Το παραπάνω διάγραμμα δείχνει το σταθμισμένο γράφημα και τη λίστα γειτνίασής του. Σημειώστε ότι υπάρχει ένας νέος χώρος στη λίστα γειτνίασης που υποδηλώνει το βάρος κάθε κόμβου.
Υλοποίηση γραφήματος σε Java
Το ακόλουθο πρόγραμμα δείχνει την εφαρμογή ενός γραφήματος στην Java. Εδώ χρησιμοποιήσαμε τη λίστα γειτνίασης για να αναπαραστήσουμε το γράφημα.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i Παραγωγή:
Γράφημα Traversal Java
Για να πραγματοποιήσουμε οποιαδήποτε ουσιαστική ενέργεια όπως αναζήτηση για την παρουσία οποιωνδήποτε δεδομένων, πρέπει να διασχίσουμε το γράφημα έτσι ώστε κάθε κορυφή και το άκρο του γραφήματος να επισκέπτονται τουλάχιστον μία φορά. Αυτό γίνεται χρησιμοποιώντας αλγόριθμους γραφημάτων που δεν είναι παρά ένα σύνολο οδηγιών που μας βοηθούν να διασχίσουμε το γράφημα.
Υπάρχουν δύο αλγόριθμοι που υποστηρίζονται για να διασχίσουν το γράφημα στην Java .
- Διαδρομή πρώτου βάθους
- Διατομή πρώτου πλάτους
Βάθος-πρώτη διέλευση
Βάθος-πρώτη αναζήτηση (DFS) είναι μια τεχνική που χρησιμοποιείται για να διασχίσει ένα δέντρο ή ένα γράφημα. Η τεχνική DFS ξεκινά με έναν ριζικό κόμβο και στη συνέχεια διασχίζει τους γειτονικούς κόμβους του ριζικού κόμβου πηγαίνοντας βαθύτερα στο γράφημα. Στην τεχνική DFS, οι κόμβοι διασχίζονται βάθος έως ότου δεν υπάρχουν άλλα παιδιά για εξερεύνηση.
Μόλις φτάσουμε στον κόμβο των φύλλων (όχι περισσότεροι θυγατρικοί κόμβοι), το DFS ακολουθεί και ξεκινά με άλλους κόμβους και πραγματοποιεί διέλευση με παρόμοιο τρόπο. Η τεχνική DFS χρησιμοποιεί μια δομή δεδομένων στοίβας για την αποθήκευση των κόμβων που διασχίζονται.
Ακολουθεί ο αλγόριθμος για την τεχνική DFS.
Αλγόριθμος
Βήμα 1: Ξεκινήστε με τον ριζικό κόμβο και τοποθετήστε τον στη στοίβα
Βήμα 2: Βάλτε το αντικείμενο από τη στοίβα και εισαγάγετε στη λίστα «επισκέφθηκε»
Βήμα 3: Για κόμβο που έχει επισημανθεί ως «επισκέφθηκε» (ή στη λίστα επισκέψεων), προσθέστε τους παρακείμενους κόμβους αυτού του κόμβου που δεν έχουν επισημανθεί ως επισκέψεις στη στοίβα.
Βήμα 4: Επαναλάβετε τα βήματα 2 και 3 έως ότου η στοίβα είναι άδεια.
Απεικόνιση της τεχνικής DFS
Τώρα θα παρουσιάσουμε την τεχνική DFS χρησιμοποιώντας ένα κατάλληλο παράδειγμα γραφήματος.
Δίνεται παρακάτω ένα παράδειγμα γραφήματος. Διατηρούμε στοίβα για την αποθήκευση εξερευνημένων κόμβων και μια λίστα για την αποθήκευση των επισκεπτόμενων κόμβων.
Θα ξεκινήσουμε με το Α για να ξεκινήσουμε, να το επισημάνουμε ως επισκέφθηκε και να το προσθέσουμε στη λίστα επισκέψεων. Στη συνέχεια, θα εξετάσουμε όλους τους γειτονικούς κόμβους του Α και θα ωθήσουμε αυτούς τους κόμβους στη στοίβα όπως φαίνεται παρακάτω.
Στη συνέχεια, ανοίγουμε έναν κόμβο από τη στοίβα, δηλαδή Β και τον επισημαίνουμε ως επισκέφθηκε. Στη συνέχεια το προσθέτουμε στη λίστα «επισκέφθηκε». Αυτό παρουσιάζεται παρακάτω.
Τώρα εξετάζουμε τους γειτονικούς κόμβους του Β που είναι Α και Γ. Από αυτό το Α έχει ήδη επισκεφτεί. Έτσι το αγνοούμε. Στη συνέχεια, βγάζουμε C από τη στοίβα. Σημείο Γ ως επισκέφθηκε. Ο γειτονικός κόμβος του C δηλ. Ε προστίθεται στη στοίβα.
Στη συνέχεια, ανοίγουμε τον επόμενο κόμβο E από τη στοίβα και τον επισημαίνουμε ως επισκέφθηκε. Ο γειτονικός κόμβος του κόμβου E είναι C που έχει ήδη επισκεφτεί. Έτσι το αγνοούμε.
Τώρα μόνο ο κόμβος D παραμένει στη στοίβα. Έτσι το χαρακτηρίζουμε ως επισκέφθηκε. Ο γειτονικός κόμβος του είναι Α που έχει ήδη επισκεφτεί. Έτσι δεν το προσθέτουμε στη στοίβα.
Σε αυτό το σημείο η στοίβα είναι άδεια. Αυτό σημαίνει ότι έχουμε ολοκληρώσει την πρώτη διάβαση βάθους για το δεδομένο γράφημα.
Η λίστα επισκέψεων δίνει την τελική ακολουθία διασταύρωσης χρησιμοποιώντας την τεχνική βάθους-πρώτης. Η τελική ακολουθία DFS για το παραπάνω γράφημα είναι A-> B-> C-> E-> D.
Υλοποίηση DFS
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list(); // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Παραγωγή:
Εφαρμογές του DFS
# 1) Εντοπίστε έναν κύκλο σε ένα γράφημα: Το DFS διευκολύνει τον εντοπισμό ενός κύκλου σε ένα γράφημα όταν μπορούμε να επιστρέψουμε σε ένα άκρο.
# 2) Μονοπάτι: Όπως έχουμε ήδη δει στην εικόνα DFS, δεδομένου οποιουδήποτε δύο κορυφών μπορούμε να βρούμε τη διαδρομή μεταξύ αυτών των δύο κορυφών.
# 3) Ελάχιστο δέντρο και μικρότερη διαδρομή: Εάν εκτελέσουμε την τεχνική DFS στο μη σταθμισμένο γράφημα, μας δίνει το ελάχιστο δέντρο έκτασης και τη συντομευμένη διαδρομή.
# 4) Τοπολογική ταξινόμηση: Η τοπολογική ταξινόμηση χρησιμοποιείται όταν πρέπει να προγραμματίσουμε τις εργασίες. Έχουμε εξαρτήσεις μεταξύ διαφόρων θέσεων εργασίας. Μπορούμε επίσης να χρησιμοποιήσουμε τοπολογική ταξινόμηση για την επίλυση εξαρτήσεων μεταξύ συνδέσμων, προγραμματιστών εντολών, σειριοποίησης δεδομένων κ.λπ.
Πρώτη διασταύρωση
Η τεχνική Breadth-first (BFS) χρησιμοποιεί μια ουρά για την αποθήκευση των κόμβων του γραφήματος. Σε αντίθεση με την τεχνική DFS, στο BFS διασχίζουμε το γράφημα ως προς το εύρος. Αυτό σημαίνει ότι διασχίζουμε το επίπεδο γραφήματος. Όταν εξερευνούμε όλες τις κορυφές ή τους κόμβους σε ένα επίπεδο προχωράμε στο επόμενο επίπεδο.
Παρακάτω δίνεται ένας αλγόριθμος για την τεχνική διέλευσης πρώτου εύρους .
Αλγόριθμος
Ας δούμε τον αλγόριθμο για την τεχνική BFS.
Δεδομένου ενός γραφήματος G για το οποίο πρέπει να εκτελέσουμε την τεχνική BFS.
- Βήμα 1: Ξεκινήστε με τον ριζικό κόμβο και τοποθετήστε τον στην ουρά.
- Βήμα 2: Επαναλάβετε τα βήματα 3 και 4 για όλους τους κόμβους στο γράφημα.
- Βήμα 3: Καταργήστε τον ριζικό κόμβο από την ουρά και προσθέστε τον στη λίστα Επισκέψεις.
- Βήμα 4: Τώρα προσθέστε όλους τους γειτονικούς κόμβους του ριζικού κόμβου στην ουρά και επαναλάβετε τα βήματα 2 έως 4 για κάθε κόμβο. (ΤΕΛΟΣ ΒΡΟΧΟΥ)
- Βήμα 6: ΕΞΟΔΟΣ
Απεικόνιση του BFS
Ας απεικονίσουμε την τεχνική BFS χρησιμοποιώντας ένα παράδειγμα γραφήματος που φαίνεται παρακάτω. Λάβετε υπόψη ότι διατηρήσαμε μια λίστα με το όνομα «Επισκέφθηκε» και μια ουρά. Χρησιμοποιούμε το ίδιο γράφημα που χρησιμοποιήσαμε στο παράδειγμα DFS για λόγους σαφήνειας.
Αρχικά, ξεκινάμε με τον root, δηλαδή τον κόμβο A και το προσθέτουμε στη λίστα επισκέψεων. Όλοι οι γειτονικοί κόμβοι του κόμβου Α, δηλαδή Β, Γ και Δ προστίθενται στην ουρά.
Στη συνέχεια, αφαιρούμε τον κόμβο Β από την ουρά. Το προσθέτουμε στη λίστα Επισκέψεις και το επισημαίνουμε ως επισκέφθηκε. Στη συνέχεια, εξερευνούμε τους παρακείμενους κόμβους του Β στην ουρά (το C βρίσκεται ήδη στην ουρά). Ένας άλλος γειτονικός κόμβος Α έχει ήδη επισκεφτεί, ώστε να τον αγνοούμε.
Στη συνέχεια, καταργούμε τον κόμβο C από την ουρά και τον επισημαίνουμε ως επισκέφθηκε. Προσθέτουμε το C στη λίστα επισκέψεων και ο παρακείμενος κόμβος E προστίθεται στην ουρά.
Στη συνέχεια, διαγράφουμε το D από την ουρά και το επισημαίνουμε ως επισκέφθηκε. Ο γειτονικός κόμβος του κόμβου D έχει ήδη επισκεφτεί, επομένως τον αγνοούμε.
Τώρα λοιπόν μόνο ο κόμβος Ε βρίσκεται στην ουρά. Το επισημαίνουμε ως επισκέφθηκε και το προσθέτουμε στη λίστα επισκέψεων. Ο γειτονικός κόμβος του Ε είναι C που έχει ήδη επισκεφθεί. Επομένως, αγνοήστε το.
Σε αυτό το σημείο, η ουρά είναι κενή και η λίστα επισκέψεων έχει την ακολουθία που αποκτήσαμε ως αποτέλεσμα της διέλευσης BFS. Η ακολουθία είναι, A-> B-> C-> D-> E.
Υλοποίηση BFS
μοιρογνωμόνιο από άκρο σε άκρο πλαίσιο δοκιμών για εφαρμογές angularjs
Το ακόλουθο πρόγραμμα Java δείχνει την εφαρμογή της τεχνικής BFS.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list(); //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Παραγωγή:
Εφαρμογές του BFS Traversal
# 1) Συλλογή απορριμμάτων: Ένας από τους αλγόριθμους που χρησιμοποιούνται από την τεχνική συλλογής απορριμμάτων για την αντιγραφή της συλλογής απορριμμάτων είναι ο 'αλγόριθμος Cheney'. Αυτός ο αλγόριθμος χρησιμοποιεί μια διασταυρούμενη πρώτη τεχνική.
# 2) Μετάδοση σε δίκτυα: Η μετάδοση πακέτων από το ένα σημείο στο άλλο σε ένα δίκτυο γίνεται χρησιμοποιώντας την τεχνική BFS.
# 3) Πλοήγηση GPS: Μπορούμε να χρησιμοποιήσουμε την τεχνική BFS για να βρούμε παρακείμενους κόμβους κατά την πλοήγηση χρησιμοποιώντας GPS.
# 4) Ιστοσελίδες κοινωνικής δικτύωσης: Η τεχνική BFS χρησιμοποιείται επίσης σε ιστότοπους κοινωνικής δικτύωσης για την εύρεση του δικτύου ατόμων που περιβάλλουν ένα συγκεκριμένο άτομο.
# 5) Συντομότερη διαδρομή και ελάχιστο δέντρο έκτασης σε μη σταθμισμένο γράφημα: Στο μη σταθμισμένο γράφημα, η τεχνική BFS μπορεί να χρησιμοποιηθεί για να βρει ένα ελάχιστο δέντρο έκτασης και τη συντομότερη διαδρομή μεταξύ των κόμβων.
Βιβλιοθήκη γραφήματος Java
Η Java δεν υποχρεώνει τους προγραμματιστές να εφαρμόζουν πάντα τα γραφήματα στο πρόγραμμα. Η Java παρέχει πολλές έτοιμες βιβλιοθήκες που μπορούν να χρησιμοποιηθούν άμεσα για τη χρήση γραφημάτων στο πρόγραμμα. Αυτές οι βιβλιοθήκες έχουν όλες τις λειτουργίες API γραφήματος που απαιτούνται για την πλήρη χρήση του γραφήματος και των διαφόρων χαρακτηριστικών του.
Δίνεται παρακάτω μια σύντομη εισαγωγή σε μερικές από τις βιβλιοθήκες γραφημάτων στην Java.
# 1) Γκουάβα Google: Το Google Guava παρέχει μια πλούσια βιβλιοθήκη που υποστηρίζει γραφήματα και αλγόριθμους, συμπεριλαμβανομένων απλών γραφημάτων, δικτύων, γραφημάτων αξίας κ.λπ.
# 2) Apache Commons: Το Apache Commons είναι ένα έργο Apache που παρέχει στοιχεία δομής δεδομένων γραφήματος και API που έχουν αλγόριθμους που λειτουργούν σε αυτήν τη δομή δεδομένων γραφήματος. Αυτά τα στοιχεία είναι επαναχρησιμοποιήσιμα.
# 3) JGraphT: Το JGraphT είναι μία από τις ευρέως χρησιμοποιούμενες βιβλιοθήκες γραφημάτων Java. Παρέχει λειτουργίες δομής δεδομένων γραφημάτων που περιέχουν απλό γράφημα, κατευθυνόμενο γράφημα, σταθμισμένο γράφημα κ.λπ. καθώς και αλγόριθμους και API που λειτουργούν στη δομή δεδομένων γραφήματος.
# 4) ΠηγήForge JUNG: Το JUNG σημαίνει «Java Universal Network / Graph» και είναι ένα πλαίσιο Java. Το JUNG παρέχει μια επεκτάσιμη γλώσσα για ανάλυση, οπτικοποίηση και μοντελοποίηση των δεδομένων που θέλουμε να αναπαρασταθούν ως γράφημα.
Το JUNG παρέχει επίσης διάφορους αλγόριθμους και ρουτίνες για αποσύνθεση, ομαδοποίηση, βελτιστοποίηση κ.λπ.
Συχνές Ερωτήσεις
Q # 1) Τι είναι ένα γράφημα στην Java;
Απάντηση: Μια δομή δεδομένων γραφήματος αποθηκεύει κυρίως συνδεδεμένα δεδομένα, για παράδειγμα, ένα δίκτυο ανθρώπων ή ένα δίκτυο πόλεων. Μια δομή δεδομένων γραφήματος αποτελείται συνήθως από κόμβους ή σημεία που ονομάζονται κορυφές. Κάθε κορυφή συνδέεται με μια άλλη κορυφή χρησιμοποιώντας συνδέσμους που ονομάζονται άκρα.
Ε # 2) Ποιοι είναι οι τύποι γραφημάτων;
Απάντηση: Παρακάτω αναφέρονται διάφοροι τύποι γραφημάτων.
- Γράφημα γραμμής: Ένα γράφημα γραμμής χρησιμοποιείται για να σχεδιάσει τις αλλαγές σε μια συγκεκριμένη ιδιότητα σε σχέση με το χρόνο.
- Ραβδόγραμμα: Τα ραβδόγραμμα συγκρίνουν τις αριθμητικές τιμές οντοτήτων όπως ο πληθυσμός σε διάφορες πόλεις, τα ποσοστά αλφαβητισμού σε ολόκληρη τη χώρα κ.λπ.
Εκτός από αυτούς τους κύριους τύπους έχουμε και άλλους τύπους όπως εικονογράφο, ιστόγραμμα, γράφημα περιοχής, διάγραμμα διασποράς κ.λπ.
Q # 3) Τι είναι ένα συνδεδεμένο γράφημα;
Απάντηση: Ένα συνδεδεμένο γράφημα είναι ένα γράφημα στο οποίο κάθε κορυφή συνδέεται με μια άλλη κορυφή. Ως εκ τούτου, στο συνδεδεμένο γράφημα, μπορούμε να φτάσουμε σε κάθε κορυφή από κάθε άλλη κορυφή.
Q # 4) Ποιες είναι οι εφαρμογές του γραφήματος;
Απάντηση: Τα γραφήματα χρησιμοποιούνται σε μια ποικιλία εφαρμογών. Το γράφημα μπορεί να χρησιμοποιηθεί για την αναπαράσταση ενός σύνθετου δικτύου. Τα γραφήματα χρησιμοποιούνται επίσης σε εφαρμογές κοινωνικής δικτύωσης για να υποδηλώσουν το δίκτυο ατόμων καθώς και για εφαρμογές όπως η εύρεση γειτονικών ατόμων ή συνδέσεων.
Τα γραφήματα χρησιμοποιούνται για να υποδηλώσουν τη ροή του υπολογισμού στην επιστήμη των υπολογιστών.
Q # 5) Πώς αποθηκεύετε ένα γράφημα;
Απάντηση: Υπάρχουν τρεις τρόποι αποθήκευσης ενός γραφήματος στη μνήμη:
# 1) Μπορούμε να αποθηκεύσουμε κόμβους ή κορυφές ως αντικείμενα και άκρα ως δείκτες.
#δύο) Μπορούμε επίσης να αποθηκεύσουμε γραφήματα ως πίνακας γειτνίασης των οποίων οι σειρές και οι στήλες είναι ίδιες με τον αριθμό των κορυφών. Η τομή κάθε σειράς και στήλης υποδηλώνει την παρουσία ή την απουσία ενός άκρου. Στο μη σταθμισμένο γράφημα, η παρουσία ενός άκρου δηλώνεται με το 1 ενώ στο σταθμισμένο γράφημα αντικαθίσταται από το βάρος του άκρου.
# 3) Η τελευταία προσέγγιση για την αποθήκευση ενός γραφήματος είναι χρησιμοποιώντας μια λίστα γειτνίασης των άκρων μεταξύ κορυφών γραφήματος ή κόμβων. Κάθε κόμβος ή κορυφή έχει τη λίστα γειτνίασης.
συμπέρασμα
Σε αυτό το σεμινάριο, συζητήσαμε λεπτομερώς γραφήματα στην Java. Εξερευνήσαμε τους διάφορους τύπους γραφημάτων, την εφαρμογή γραφημάτων και τεχνικές διέλευσης. Τα γραφήματα μπορούν να χρησιμοποιηθούν για την εύρεση της συντομότερης διαδρομής μεταξύ των κόμβων.
Στα επερχόμενα σεμινάρια μας, θα συνεχίσουμε να διερευνούμε γραφήματα συζητώντας μερικούς τρόπους εύρεσης της πιο σύντομης διαδρομής.
=> Παρακολουθήστε εδώ την απλή εκπαίδευση Java.
Συνιστώμενη ανάγνωση
- Εκμάθηση Java Reflection με παραδείγματα
- Πώς να εφαρμόσετε τον αλγόριθμο της Dijkstra στην Java
- Εκμάθηση Java SWING: Container, Components and Event Handling
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
- TreeMap In Java - Tutorial with Java TreeMap Παραδείγματα
- Πρόσβαση τροποποιητών σε Java - Εκμάθηση με παραδείγματα
- Java String με String Buffer και String Builder Tutorial
- Το Java String περιέχει () Μέθοδος Εκμάθησης με Παραδείγματα
