Δομή δεδομένων γραφήματος και Algorithms (Παράδειγμα)
Σάρα Τσεν
⚡ Έξυπνη Σύνοψη
Η Δομή Δεδομένων Γραφήματος είναι μια μη γραμμική συλλογή κορυφών και ακμών όπου κάθε ακμή συνδέει ένα ζεύγος κορυφών. Τα γραφήματα μοντελοποιούν δίκτυα πραγματικού κόσμου, όπως χάρτες, κοινωνικές συνδέσεις και ιστοσελίδες, και υποστηρίζουν πολλούς ισχυρούς αλγόριθμους.
Τι είναι ένα γράφημα στη δομή δεδομένων;
Ένα γράφημα είναι μια μη γραμμική δομή δεδομένων που αποτελείται από κορυφές και ακμές, όπου οι κορυφές περιέχουν τις πληροφορίες ή τα δεδομένα και οι ακμές λειτουργούν ως σύνδεσμος μεταξύ ενός ζεύγους κορυφών.
Χρησιμοποιείται για την επίλυση πραγματικών προβλημάτων, όπως η εύρεση της καλύτερης διαδρομής προς την τοποθεσία προορισμού και η διαδρομή για τηλεπικοινωνίες και κοινωνικά δίκτυα. Οι χρήστες θεωρούνται κόμβοι στο Γράφημα και τα καλώδια είναι οι ακμές που συνδέουν τους χρήστες.
Εάν οι ακμές αντιπροσωπεύονται ως Ε και οι κορυφές ως V, τότε το γράφημα G μπορεί να γραφτεί ως το σύνολο των κορυφών και των ακμών, όπως π.χ. Σολ (V, E).
Παράδειγμα Γραφήματος στη Δομή Δεδομένων
Ακολουθεί ένα απλό παράδειγμα δομής δεδομένων γραφήματος:
Είναι ένα απλό μη κατευθυνόμενο γράφημα (ένα είδος γραφήματος). Εδώ το σύνολο των κορυφών είναι: {A, B, C, D, E, F}. Δύο κορυφές δημιουργούν μια ακμή. Για παράδειγμα, τα A και B συνδέονται με μια ακμή. Ωστόσο, τα A και F δεν συνδέονται με καμία ακμή.
Γραφικές ορολογίες στη δομή δεδομένων
Οι ακόλουθοι είναι μερικοί σημαντικοί όροι που χρησιμοποιούνται στη δομή δεδομένων γραφήματος:
| Όρος | Περιγραφή |
|---|---|
| Κορυφή | Κάθε στοιχείο δεδομένων ονομάζεται κορυφή ή κόμβος. Στην παραπάνω εικόνα, οι κορυφές A, B, C, D και E είναι οι κορυφές. |
| Άκρη (τόξο) | Οι σύνδεσμοι σύνδεσης μεταξύ δύο κόμβων ή κορυφών ονομάζονται ακμή (Arc). Έχει δύο άκρα και αναπαρίσταται ως (startingVertex, endingVertex). |
| Μη κατευθυνόμενη άκρη | Είναι μια αμφίδρομη άκρη. |
| Σκηνοθετημένος Edge | Είναι ένα άκρο μονής κατεύθυνσης. |
| Ζυγισμένη άκρη | Ένα πλεονέκτημα με μια αξία πάνω του. |
| Πτυχίο | Σε ένα γράφημα, ο αριθμός των ακμών που συνδέονται με μια κορυφή ονομάζεται βαθμός. |
| Πτυχίο | Ο συνολικός αριθμός των εισερχόμενων άκρων που συνδέονται σε μια κορυφή. |
| Ανώτερος βαθμός | Ο συνολικός αριθμός των εξερχόμενων άκρων που συνδέονται σε μια κορυφή. |
| Αυτο-βρόχος | Μια ακμή ονομάζεται αυτο-βρόχος εάν τα δύο τελικά της σημεία συμπίπτουν. |
| Γειτνίαση | Οι κορυφές λέγονται γειτονικές αν υπάρχει μια ακμή που συνδέεται μεταξύ τους. |
Τύποι Γραφημάτων στη Δομή Δεδομένων
Εδώ είναι η λίστα με τα πιο κοινά τύπους γραφημάτων στη δομή δεδομένων:
- Σκηνοθετημένη Γράφημα
- Μη κατευθυνόμενο γράφημα
- Σταθμισμένο γράφημα
- Γράφημα διπλής κατεύθυνσης
- Άπειρο γράφημα
- Μηδενικό γράφημα
- Ασήμαντο γράφημα
- Πολλαπλό γράφημα
- Πλήρες γράφημα
- Συνδεδεμένο γράφημα
- Κυκλικό Γράφημα
- Κατευθυνόμενο ακυκλικό γράφημα (DAG)
- Γράφημα κύκλου
- Διμερές γράφημα
- Γράφημα Euler
- Γράφημα Hamilton
Πώς να αναπαραστήσετε ένα γράφημα σε δομή δεδομένων;
Ένα γράφημα αποθηκεύεται συνήθως στη μνήμη χρησιμοποιώντας μία από τις δύο αναπαραστάσεις. Η επιλογή επηρεάζει την ποσότητα μνήμης που χρησιμοποιεί το γράφημα και την ταχύτητα εκτέλεσης των συνηθισμένων λειτουργιών.
- Πίνακας Γειτνίασης: Ένας δισδιάστατος πίνακας V × V όπου το κελί [i][j] είναι 1 (ή το βάρος της ακμής) εάν υπάρχει ακμή μεταξύ της κορυφής i και της κορυφής j, και 0 διαφορετικά. Επιτρέπει την αναζήτηση ακμής O(1) αλλά χρησιμοποιεί χώρο O(V²), καθιστώντας το ιδανικό για πυκνά γραφήματα.
- Λίστα Γειτονιάς: Ένας πίνακας λιστών όπου κάθε κορυφή αποθηκεύει μια λίστα με τις γειτονικές της κορυφές. Χρησιμοποιεί χώρο O(V + E) και είναι αποτελεσματικός για αραιά γραφήματα, γι' αυτό και τα περισσότερα γραφήματα του πραγματικού κόσμου το χρησιμοποιούν.
Μπορείτε να διαβάσετε περισσότερα σχετικά με αυτά στο λίστα γειτνίασης και αναπαράσταση πίνακα ενός γραφήματος tutorial.
Εφαρμογές Δομής Δεδομένων Γραφημάτων
Ένα γράφημα έχει πολλές περιπτώσεις χρήσης. Υπάρχουν πολλοί αλγόριθμοι που χρησιμοποιούν Γραφήματα. Ακολουθούν μερικές από τις εφαρμογές του Γράφου:
- Google Οι Χάρτες χρησιμοποιούν γραφήματα για να βρουν τη διασταύρωση δύο δρόμων και να υπολογίσουν την απόσταση μεταξύ δύο τοποθεσιών. Για παράδειγμα, Dijkstra, για την εύρεση της μικρότερης απόστασης μεταξύ της τοποθεσίας προέλευσης και του προορισμού.
- Το Facebook χρησιμοποιεί Γραφήματα για να βρει τους κοινούς φίλους των χρηστών. Ο αλγόριθμός του θεωρεί κάθε χρήστη ως κόμβο ενός γραφήματος.
- Για την κατανομή πόρων, χρησιμοποιείται ένα DAG (Directed Acyclic Graph - Κατευθυνόμενο Ακυκλικό Γράφημα). Ελέγχει την εξάρτηση των πόρων.
- The Google Οι μηχανές αναζήτησης χρησιμοποιούν γραφήματα για να δημιουργήσουν την κατάταξη των ιστοσελίδων.
- Ενας χάρτηςping Η συσκευή χρησιμοποιεί τη δομή δεδομένων γραφήματος.
- A router και το πρωτόκολλό του χρησιμοποιούν το Γράφημα για να μάθουν τη διαδρομή προς τον προορισμό.
