Δομή δεδομένων γραφήματος και Algorithms (Παράδειγμα)
Σάρα Τσεν
Τι είναι ένα γράφημα στη δομή δεδομένων;
Ένα γράφημα είναι μια μη γραμμική δομή δεδομένων που αποτελείται από κορυφές και ακμές, όπου οι κορυφές περιέχουν τις πληροφορίες ή τα δεδομένα και οι ακμές λειτουργούν ως σύνδεσμος μεταξύ ζεύγους κορυφών.
Χρησιμοποιείται για την επίλυση πραγματικών προβλημάτων λέξεων, όπως η εύρεση της καλύτερης διαδρομής προς την τοποθεσία προορισμού και η διαδρομή για τηλεπικοινωνίες και κοινωνικά δίκτυα. Οι χρήστες θεωρούνται κόμβος στο Γράφημα και τα καλώδια είναι τα άκρα που συνδέουν τους χρήστες.
Εάν οι ακμές αντιπροσωπεύονται ως Ε και οι κορυφές ως V, τότε το γράφημα G μπορεί να γραφτεί ως το σύνολο των κορυφών και των ακμών, όπως π.χ. G (V, E)
Παράδειγμα Γραφήματος στη Δομή Δεδομένων
Ακολουθεί ένα απλό παράδειγμα δομής δεδομένων γραφήματος:
Είναι ένα απλό μη κατευθυνόμενο γράφημα (ένα είδος Γραφήματος). Εδώ το σύνολο της κορυφής είναι: {A, B, C, D, E, F}. Δύο κορυφές δημιουργούν μια άκρη. Για παράδειγμα, τα Α και Β συνδέονται με μια ακμή. Ωστόσο, τα A και F δεν συνδέονται με καμία ακμή.
Γραφικές ορολογίες στη δομή δεδομένων
Ακολουθούν ορισμένοι σημαντικοί όροι που χρησιμοποιούνται στη δομή δεδομένων γραφήματος:
| Όρος | Descriptιόν |
|---|---|
| Κορυφή | Όλα τα στοιχεία δεδομένων ονομάζονται κορυφή ή κόμβος. Στην παραπάνω εικόνα, τα A, B, C, D & E είναι οι κορυφές. |
| Άκρη (τόξο) | Οι συνδετικοί σύνδεσμοι μεταξύ δύο κόμβων ή κορυφών ονομάζονται ακμή (Arc). Έχει δύο άκρα και αναπαρίσταται ως (startingVertex, endingVertex). |
| Μη κατευθυνόμενη άκρη | Είναι μια αμφίδρομη άκρη. |
| Σκηνοθετημένος Edge | Είναι ένα άκρο μονής κατεύθυνσης. |
| Ζυγισμένη άκρη | Μια άκρη με αξία. |
| Πτυχίο | Στο Graph, ο αριθμός των ακμών που συνδέονται σε μια κορυφή ονομάζεται μοίρα. |
| Πτυχίο | Ο συνολικός αριθμός των εισερχόμενων άκρων που συνδέονται σε μια κορυφή. |
| Ανώτερος βαθμός | Ο συνολικός αριθμός των εξερχόμενων άκρων που συνδέονται σε μια κορυφή. |
| Αυτο-βρόχος | Μια ακμή ονομάζεται αυτο-βρόχος εάν τα δύο τελικά της σημεία συμπίπτουν. |
| Γειτνίαση | Οι κορυφές λέγονται γειτονικές εάν είναι συνδεδεμένη μια άκρη. |
Τύποι Γραφημάτων στη Δομή Δεδομένων
Εδώ είναι η λίστα με τα πιο κοινά τύπους γραφημάτων στη δομή δεδομένων:
- Σκηνοθετημένη Γράφημα
- Μη κατευθυνόμενο γράφημα
- Σταθμισμένο γράφημα
- Γράφημα διπλής κατεύθυνσης
- Άπειρο γράφημα
- Μηδενικό γράφημα
- Ασήμαντο γράφημα
- Πολλαπλό γράφημα
- Πλήρες γράφημα
- Συνδεδεμένο γράφημα
- Κυκλικό Γράφημα
- Κατευθυνόμενο ακυκλικό γράφημα (DAG)
- Γράφημα κύκλου
- Διμερές γράφημα
- Γράφημα Euler
- Γράφημα Hamilton
Εφαρμογές Δομής Δεδομένων Γραφημάτων
Ένα γράφημα έχει πολλές περιπτώσεις χρήσης. Υπάρχουν πολλοί αλγόριθμοι που χρησιμοποιούν πολύ γραφήματα. Ακολουθούν μερικές από τις εφαρμογές του Γραφήματος:
- Το Google Maps χρησιμοποιεί γραφήματα για να βρει τη διασταύρωση δύο δρόμων και να υπολογίσει την απόσταση μεταξύ δύο τοποθεσιών.
Για παράδειγμα, Dijkstra, για την εύρεση της μικρότερης απόστασης μεταξύ της τοποθεσίας πηγής και προορισμού. - Το Facebook χρησιμοποιεί γραφήματα για να βρει τον κοινό φίλο των χρηστών. Ο αλγόριθμός του θεωρεί κάθε χρήστη ως κόμβο ενός γραφήματος.
- Για την κατανομή πόρων, χρησιμοποιείται το DAG (Direct Acyclic Graph). Ελέγχει την εξάρτηση των πόρων.
- Η μηχανή αναζήτησης Google χρησιμοποιεί γραφήματα για να δημιουργήσει την κατάταξη για ιστότοπους.
- Μια συσκευή χαρτογράφησης χρησιμοποιεί τη δομή δεδομένων γραφήματος.
- router και το πρωτόκολλο t χρησιμοποιεί το γράφημα για να μάθει τη διαδρομή της διαδρομής προορισμού.
