Δομή δεδομένων γραφήματος

Πίνακας περιεχομένων

Ορολογία γραφήματος
Αναπαράσταση γραφήματος
Λειτουργίες γραφήματος

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

Μια δομή δεδομένων γραφήματος είναι μια συλλογή κόμβων που έχουν δεδομένα και συνδέονται με άλλους κόμβους.

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

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

Παράδειγμα δομής δεδομένων γραφήματος

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

Πιο συγκεκριμένα, ένα γράφημα είναι μια δομή δεδομένων (V, E) που αποτελείται από

Μια συλλογή κορυφών V
Μια συλλογή ακμών Ε, που αντιπροσωπεύεται ως ταξινομημένα ζεύγη κορυφών (u, v)

Οι κορυφές και τα άκρα

Στο γράφημα,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Ορολογία γραφήματος

Ευθυγράμμιση : Μια κορυφή λέγεται ότι είναι δίπλα σε άλλη κορυφή εάν υπάρχει ένα άκρο που τα συνδέει. Οι κορυφές 2 και 3 δεν γειτνιάζουν επειδή δεν υπάρχει άκρη μεταξύ τους.
Διαδρομή : Μια ακολουθία ακμών που σας επιτρέπει να μεταβείτε από την κορυφή Α στην κορυφή Β ονομάζεται διαδρομή. Τα 0-1, 1-2 και 0-2 είναι διαδρομές από την κορυφή 0 έως την κορυφή 2.
Κατευθυνόμενο γράφημα : Ένα γράφημα στο οποίο ένα άκρο (u, v) δεν σημαίνει απαραίτητα ότι υπάρχει και ένα άκρο (v, u). Τα άκρα σε ένα τέτοιο γράφημα παριστάνονται με βέλη για να δείξουν την κατεύθυνση του άκρου.

Αναπαράσταση γραφήματος

Τα γραφήματα παρουσιάζονται συνήθως με δύο τρόπους:

1. Πίνακας προσαρμογής

Ένας πίνακας γειτνίασης είναι ένας πίνακας 2D με κορυφές V x V. Κάθε σειρά και στήλη αντιπροσωπεύουν μια κορυφή.

Εάν η τιμή οποιουδήποτε στοιχείου a(i)(j)είναι 1, αντιπροσωπεύει ότι υπάρχει μια ακμή που συνδέει την κορυφή i και την κορυφή j.

Ο πίνακας γειτνίασης για το γράφημα που δημιουργήσαμε παραπάνω είναι

Πίνακας γειτνίασης γραφήματος

Δεδομένου ότι είναι ένα μη κατευθυνόμενο γράφημα, για το άκρο (0,2), πρέπει επίσης να επισημάνουμε το άκρο (2,0). κάνοντας τη μήτρα γειτονίας συμμετρική για τη διαγώνια.

Η αναζήτηση άκρων (ο έλεγχος εάν υπάρχει ένα άκρο μεταξύ της κορυφής Α και της κορυφής Β) είναι εξαιρετικά γρήγορη στην αναπαράσταση της μήτρας γειτνίασης, αλλά πρέπει να διατηρήσουμε χώρο για κάθε πιθανή σύνδεση μεταξύ όλων των κορυφών (V x V), επομένως απαιτεί περισσότερο χώρο.

2. Λίστα ικανοτήτων

Μια λίστα γειτνίασης αντιπροσωπεύει ένα γράφημα ως μια σειρά συνδεδεμένων λιστών.

Ο δείκτης του πίνακα αντιπροσωπεύει μια κορυφή και κάθε στοιχείο στη συνδεδεμένη λίστα του αντιπροσωπεύει τις άλλες κορυφές που σχηματίζουν ένα άκρο με την κορυφή.

Η λίστα γειτνίασης με το γράφημα που δημιουργήσαμε στο πρώτο παράδειγμα είναι η εξής:

Αναπαράσταση λίστας προσαρμογής

Μια λίστα γειτνίασης είναι αποτελεσματική από την άποψη του χώρου αποθήκευσης, επειδή πρέπει να αποθηκεύουμε μόνο τις τιμές για τις άκρες. Για ένα γράφημα με εκατομμύρια κορυφές, αυτό μπορεί να σημαίνει πολύ αποθηκευμένο χώρο.