Γεια σε όλους.
Σε αυτό το σημείωμα, αποφάσισα να απαριθμήσω τις κύριες δομές δεδομένων που χρησιμοποιούνται για την αποθήκευση γραφημάτων στην επιστήμη των υπολογιστών και θα μιλήσω επίσης για μερικές ακόμη τέτοιες δομές που κατά κάποιο τρόπο «κρυσταλλώθηκαν» για μένα.
Λοιπόν, ας ξεκινήσουμε. Αλλά όχι από την αρχή - νομίζω ότι όλοι γνωρίζουμε ήδη τι είναι ένα γράφημα και τι είναι (κατευθυνόμενο, μη κατευθυνόμενο, σταθμισμένο, μη σταθμισμένο, με ή χωρίς πολλαπλές ακμές και βρόχους).
Λοιπόν πάμε. Τι επιλογές για δομές δεδομένων για «αποθήκευση γραφημάτων» έχουμε;
1. Δομές δεδομένων μήτρας
1.1 Πίνακας γειτνίασης. Ο πίνακας γειτνίασης είναι ένας πίνακας όπου οι επικεφαλίδες σειρών και στηλών αντιστοιχούν στους αριθμούς των κορυφών του γραφήματος και η τιμή καθενός από τα στοιχεία του a(i,j) καθορίζεται από την παρουσία ή την απουσία ακμών μεταξύ των κορυφών. i και j (είναι σαφές ότι για ένα μη κατευθυνόμενο γράφημα ένας τέτοιος πίνακας θα είναι συμμετρικός ή μπορούμε να συμφωνήσουμε ότι αποθηκεύουμε όλες τις τιμές μόνο πάνω από την κύρια διαγώνιο). Για μη σταθμισμένα γραφήματα, το a(i,j) μπορεί να οριστεί από τον αριθμό των ακμών από i έως j (αν δεν υπάρχει τέτοια ακμή, τότε a(i,j)= 0), και για σταθμισμένα γραφήματα, επίσης με το βάρος (συνολικό βάρος) των αναφερόμενων άκρων.
1.2 Πίνακας επίπτωσης. Σε αυτήν την περίπτωση, το γράφημά μας αποθηκεύεται επίσης σε έναν πίνακα στον οποίο, κατά κανόνα, οι αριθμοί σειρών αντιστοιχούν στους αριθμούς των κορυφών του και οι αριθμοί στηλών αντιστοιχούν σε προ-αριθμημένες ακμές. Εάν μια κορυφή και μια ακμή προσπίπτουν μεταξύ τους, τότε γράφεται μια μη μηδενική τιμή στο αντίστοιχο κελί (για μη κατευθυνόμενα γραφήματα, γράφεται 1 εάν η κορυφή και η άκρη είναι προσπίπτουσες, για τα προσανατολισμένα γραφήματα - "1" εάν η ακμή "Έξοδος" από την κορυφή και "-1" εάν "περιλαμβάνει" σε αυτήν (είναι αρκετά εύκολο να το θυμάστε, επειδή το σύμβολο "μείον" φαίνεται επίσης να "περιλαμβάνεται" στον αριθμό "-1")). Για σταθμισμένα γραφήματα, πάλι, αντί για 1 και -1, μπορείτε να καθορίσετε το συνολικό βάρος της άκρης.
2. Δομές δεδομένων απαρίθμησης
2.1 Λίστα γειτνίασης. Λοιπόν, όλα φαίνεται να είναι απλά εδώ. Κάθε κορυφή του γραφήματος μπορεί, γενικά, να συσχετιστεί με οποιαδήποτε δομή απαρίθμησης (λίστα, διάνυσμα, πίνακας, ...), η οποία θα αποθηκεύει τους αριθμούς όλων των κορυφών που γειτνιάζουν με τη δεδομένη. Για κατευθυνόμενα γραφήματα, θα προσθέσουμε σε μια τέτοια λίστα μόνο εκείνες τις κορυφές στις οποίες υπάρχει μια «κατευθυνόμενη» άκρη από μια κορυφή χαρακτηριστικών. Για σταθμισμένα γραφήματα η υλοποίηση θα είναι πιο περίπλοκη.
2.2 Λίστα πλευρών. Αρκετά δημοφιλής δομή δεδομένων. Η λίστα των ακμών, όπως μας λέει ο Captain Obviousness, είναι στην πραγματικότητα μια λίστα με άκρες του γραφήματος, καθεμία από τις οποίες καθορίζεται από την αρχική κορυφή, την κορυφή του τερματισμού (για μη κατευθυνόμενα γραφήματα η σειρά δεν είναι σημαντική εδώ, αν και για ενοποίηση μπορείτε χρησιμοποιήστε διάφορους κανόνες, για παράδειγμα, προσδιορίζοντας τις κορυφές με σειρά αύξησης) και το βάρος (μόνο για σταθμισμένα γραφήματα).
Μπορείτε να δείτε τις λίστες matrix που αναφέρονται παραπάνω με περισσότερες λεπτομέρειες (και με εικόνες), για παράδειγμα, .
2.3 Συστοιχία γειτνίασης. Δεν είναι η πιο κοινή δομή. Στον πυρήνα του, είναι μια μορφή «συσκευασίας» λιστών γειτνίασης σε μια δομή απαρίθμησης (πίνακας, διάνυσμα). Τα πρώτα n (σύμφωνα με τον αριθμό των κορυφών του γραφήματος) στοιχεία ενός τέτοιου πίνακα περιέχουν τους αρχικούς δείκτες του ίδιου πίνακα, ξεκινώντας από τους οποίους όλες οι κορυφές που γειτνιάζουν με τη δεδομένη γράφονται σε μια σειρά.
Εδώ βρήκα την πιο κατανοητή (για τον εαυτό μου) εξήγηση:
3. Διάνυσμα γειτνίασης και συσχετικός πίνακας γειτνίασης
Αποδείχθηκε ότι ο συγγραφέας αυτών των γραμμών, που δεν ήταν επαγγελματίας προγραμματιστής, αλλά που ασχολήθηκε περιοδικά με γραφήματα, ασχολήθηκε συχνότερα με λίστες ακμών. Πράγματι, είναι βολικό εάν το γράφημα έχει πολλαπλούς βρόχους και ακμές. Και έτσι, κατά την ανάπτυξη των κλασικών λιστών ακμών, προτείνω να δώσουμε προσοχή στην «ανάπτυξη/κλάδο/τροποποίηση/μετάλλαξή τους», δηλαδή: το διάνυσμα γειτνίασης και τον συσχετιστικό πίνακα γειτνίασης.
3.1 Διάνυσμα γειτνίασης
Περίπτωση (a1): μη σταθμισμένο γράφημα
Θα ονομάσουμε διάνυσμα γειτνίασης για ένα μη σταθμισμένο γράφημα ένα διατεταγμένο σύνολο ζυγού αριθμού ακεραίων (a[2i], a[2i+1],..., όπου το i αριθμείται c 0), στο οποίο κάθε ζεύγος αριθμών είναι a[2i], το a[2i+1 ] καθορίζει μια ακμή γραφήματος μεταξύ των κορυφών a[2i] και a[2i+1], αντίστοιχα.
Αυτή η μορφή εγγραφής δεν περιέχει πληροφορίες σχετικά με το εάν το γράφημα είναι κατευθυνόμενο (και οι δύο επιλογές είναι δυνατές). Όταν χρησιμοποιείτε τη μορφή διγράφου, η άκρη θεωρείται ότι κατευθύνεται από το a[2i] στο a[2i+1]. Εδώ και παρακάτω: για μη κατευθυνόμενα γραφήματα, εάν είναι απαραίτητο, μπορούν να εφαρμοστούν απαιτήσεις για τη σειρά καταγραφής κορυφών (για παράδειγμα, ότι η κορυφή με τη χαμηλότερη τιμή του αριθμού που της έχει εκχωρηθεί είναι πρώτη).
Στη C++, συνιστάται να καθορίσετε ένα διάνυσμα γειτνίασης χρησιμοποιώντας std:: vector, εξ ου και το όνομα αυτής της δομής δεδομένων.
Περίπτωση (a2): μη σταθμισμένο γράφημα, τα βάρη ακμών είναι ακέραιοι
Κατ' αναλογία με την περίπτωση (a1), ονομάζουμε το διάνυσμα γειτνίασης για ένα σταθμισμένο γράφημα με βάρη ακέραιων ακμών ένα διατεταγμένο σύνολο (δυναμικός πίνακας) αριθμών (a[3i], a[3i+1], a[3i+2], ..., όπου i αριθμείται c 0), όπου κάθε «τριπλή» αριθμών a[3i], a[3i+1], a[3i+2] καθορίζει μια ακμή του γραφήματος μεταξύ των κορυφών με αριθμό a[3i] και a[3i+1], αντίστοιχα, και η τιμή a [3i+2] είναι το βάρος αυτής της ακμής. Ένα τέτοιο γράφημα μπορεί επίσης να είναι είτε κατευθυνόμενο είτε όχι.
Περίπτωση (β): μη σταθμισμένο γράφημα, μη ακέραια βάρη ακμών
Δεδομένου ότι είναι αδύνατο να αποθηκευτούν ετερογενή στοιχεία σε έναν πίνακα (διάνυσμα), για παράδειγμα, είναι δυνατή η ακόλουθη υλοποίηση. Το γράφημα αποθηκεύεται σε ένα ζεύγος διανυσμάτων, στα οποία το πρώτο διάνυσμα είναι το διάνυσμα γειτνίασης του γραφήματος χωρίς να προσδιορίζονται τα βάρη και το δεύτερο διάνυσμα περιέχει τα αντίστοιχα βάρη (πιθανή υλοποίηση για C++: std::pair ). Έτσι, για μια ακμή που ορίζεται από ένα ζεύγος κορυφών κάτω από τους δείκτες 2i, 2i+1 του πρώτου διανύσματος, το βάρος θα είναι ίσο με το στοιχείο κάτω από τον δείκτη i του δεύτερου διανύσματος.
Λοιπόν, γιατί είναι απαραίτητο αυτό;
Λοιπόν, ο συγγραφέας αυτών των γραμμών το βρήκε αρκετά χρήσιμο για την επίλυση ορισμένων προβλημάτων. Λοιπόν, από τυπική άποψη, θα υπάρχουν τα ακόλουθα πλεονεκτήματα:
- Το διάνυσμα γειτνίασης, όπως κάθε άλλη «αριθμητική» δομή, είναι αρκετά συμπαγές, καταλαμβάνει λιγότερη μνήμη από τον πίνακα γειτνίασης (για αραιά γραφήματα) και είναι σχετικά εύκολο να εφαρμοστεί.
- Οι κορυφές του γραφήματος, καταρχήν, μπορούν επίσης να σημειωθούν με αρνητικούς αριθμούς. Κι αν χρειάζεται μια τέτοια «διαστροφή»;
- Τα γραφήματα μπορούν να περιέχουν πολλαπλές ακμές και πολλαπλούς βρόχους, με διαφορετικά βάρη (θετικά, αρνητικά, ακόμη και μηδενικά). Δεν υπάρχουν περιορισμοί εδώ.
- Μπορείτε επίσης να αντιστοιχίσετε διαφορετικές ιδιότητες σε άκρες - αλλά για περισσότερα σχετικά, δείτε την ενότητα 4.
Ωστόσο, πρέπει να παραδεχτούμε ότι αυτή η «λίστα» δεν συνεπάγεται γρήγορη πρόσβαση στην άκρη. Και εδώ έρχεται στη διάσωση η Associative Adjacency Array, η οποία συζητείται παρακάτω.
3.2 Συσχετικός πίνακας γειτνίασης
Έτσι, εάν η πρόσβαση σε ένα συγκεκριμένο άκρο, το βάρος του και άλλες ιδιότητες είναι κρίσιμες για εμάς και οι απαιτήσεις μνήμης δεν μας επιτρέπουν να χρησιμοποιήσουμε τον πίνακα γειτνίασης, τότε ας σκεφτούμε πώς μπορούμε να αλλάξουμε το διάνυσμα γειτνίασης για να λύσουμε αυτό το πρόβλημα. Έτσι, το κλειδί είναι ένα άκρο του γραφήματος, το οποίο μπορεί να καθοριστεί ως διατεταγμένο ζεύγος ακεραίων. Πώς μοιάζει αυτό; Δεν είναι κλειδί σε έναν συσχετιστικό πίνακα; Και, αν ναι, γιατί δεν το εφαρμόζουμε; Ας έχουμε έναν συσχετιστικό πίνακα όπου κάθε κλειδί - ένα διατεταγμένο ζεύγος ακεραίων - θα συσχετίζεται με μια τιμή - έναν ακέραιο ή έναν πραγματικό αριθμό που καθορίζει το βάρος της ακμής. Στη C++, συνιστάται η υλοποίηση αυτής της δομής με βάση το κοντέινερ std::map (std::map , int> ή std::map , double>), ή std::multimap εάν αναμένονται πολλαπλές ακμές. Λοιπόν, έχουμε μια δομή για την αποθήκευση γραφημάτων που καταλαμβάνει λιγότερη μνήμη από τις δομές «μήτρας», μπορεί να ορίσει γραφήματα με πολλαπλούς βρόχους και ακμές και δεν έχει καν αυστηρές απαιτήσεις για τη μη αρνητικότητα των αριθμών κορυφής (δεν ξέρω ποιος το χρειάζεται αυτό, αλλά ακόμα).
4. Οι δομές δεδομένων είναι γεμάτες, αλλά κάτι λείπει
Και είναι αλήθεια: κατά την επίλυση ορισμένων προβλημάτων, ίσως χρειαστεί να αντιστοιχίσουμε ορισμένα χαρακτηριστικά στις άκρες του γραφήματος και, κατά συνέπεια, να τα αποθηκεύσουμε. Εάν είναι δυνατό να μειωθούν αναμφισβήτητα αυτά τα χαρακτηριστικά σε ακέραιους αριθμούς, τότε είναι δυνατή η αποθήκευση τέτοιων «γραφημάτων με πρόσθετα χαρακτηριστικά» χρησιμοποιώντας εκτεταμένες εκδόσεις του διανύσματος γειτνίασης και του συσχετιστικού πίνακα γειτνίασης.
Ας έχουμε λοιπόν ένα μη σταθμισμένο γράφημα, για κάθε ακμή του οποίου είναι απαραίτητο να αποθηκεύονται, για παράδειγμα, 2 πρόσθετα χαρακτηριστικά που καθορίζονται από ακέραιους αριθμούς. Σε αυτήν την περίπτωση, είναι δυνατό να ορίσουμε το διάνυσμα γειτνίασης ως ένα διατεταγμένο σύνολο όχι «ζευγών», αλλά «τετράγωνων» ακεραίων αριθμών (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , όπου τα a[2i+2] και a[2i+3] θα καθορίσουν τα χαρακτηριστικά της αντίστοιχης ακμής. Για ένα γράφημα με ακέραια βάρη ακμών, η σειρά είναι γενικά παρόμοια (η μόνη διαφορά θα είναι ότι τα χαρακτηριστικά θα ακολουθούν το βάρος της ακμής και θα καθορίζονται από τα στοιχεία a[2i+3] και a[2i+4] , και η ίδια η άκρη θα καθοριστεί όχι 4, αλλά 5 διατεταγμένοι αριθμοί). Και για ένα γράφημα με μη ακέραια βάρη ακμών, τα χαρακτηριστικά μπορούν να εγγραφούν στο μη σταθμισμένο στοιχείο του.
Όταν χρησιμοποιείται ένας συσχετιστικός πίνακας γειτνίασης για γραφήματα με βάρη ακέραιων ακμών, είναι δυνατό να καθοριστεί ως τιμή όχι ένας μεμονωμένος αριθμός, αλλά ένας πίνακας (διάνυσμα) αριθμών που καθορίζουν, εκτός από το βάρος μιας ακμής, όλα τα άλλα απαραίτητα χαρακτηριστικά. Ταυτόχρονα, μια ταλαιπωρία για την περίπτωση των μη ακέραιων βαρών θα είναι η ανάγκη να καθορίσετε ένα σύμβολο με αριθμό κινητής υποδιαστολής (ναι, αυτό είναι μια ταλαιπωρία, αλλά αν δεν υπάρχουν τόσα πολλά τέτοια σημάδια και αν δεν βάλτε τα πολύ «δύσκολα» διπλά, τότε μπορεί να μην είναι τίποτα) . Αυτό σημαίνει ότι στην C++ οι εκτεταμένοι συσχετιστικοί πίνακες γειτνίασης μπορούν να οριστούν ως εξής: std::map , std::vector> ή std::map , std::διάνυσμα, στο οποίο η πρώτη τιμή στο «κλειδί-τιμή-διάνυσμα» θα είναι το βάρος της άκρης και στη συνέχεια εντοπίζονται οι αριθμητικοί προσδιορισμοί των χαρακτηριστικών του.
Λογοτεχνία:
Σχετικά με τα γραφήματα και τους αλγόριθμους γενικά:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Αλγόριθμοι: κατασκευή και ανάλυση, 2η έκδοση: Μετάφρ. από τα Αγγλικά – M.: Williams Publishing House, 2011.
2. Harari Frank. Θεωρία γραφημάτων. Μ.: Μιρ, 1973.
Η αναφορά του συγγραφέα σχετικά με αυτές τις ίδιες διανυσματικές και συνειρμικές συστοιχίες γειτονιών:
3. Chernoukhov S.A. Διάνυσμα γειτνίασης και συσχετιστικός πίνακας γειτνίασης ως τρόποι αναπαράστασης και αποθήκευσης γραφημάτων / SA Chernouhov. Διάνυσμα γειτνίασης και χάρτης γειτνίασης ως δομές δεδομένων για την αναπαράσταση γραφήματος // Συλλογή άρθρων του Διεθνούς Επιστημονικού και Πρακτικού Συνεδρίου «Προβλήματα εφαρμογής των αποτελεσμάτων καινοτόμων εξελίξεων και τρόποι επίλυσής τους» (Saratov, 14.09.2019 Σεπτεμβρίου 2019). – Sterlitamak: AMI, 65, σελ. 69-XNUMX
Χρήσιμες διαδικτυακές πηγές για το θέμα:
4.
5.
Πηγή: www.habr.com