Τύποι γραφημάτων στη δομή δεδομένων με παραδείγματα
Σάρα Τσεν
⚡ Έξυπνη Σύνοψη
Τα γραφήματα στη δομή δεδομένων είναι μη γραμμικές συλλογές κορυφών και ακμών που ταξινομούνται σε οικογένειες όπως κατευθυνόμενα, μη κατευθυνόμενα, σταθμισμένα, κυκλικά, ακυκλικά, πλήρη, συνδεδεμένα, διμερή, γραφήματα Euler και Hamilton με βάση τη δομή.
Ένα γράφημα είναι μια μη γραμμική δομή δεδομένων που αποτελείται από κορυφές και ακμές. Οι κορυφές περιέχουν τις πληροφορίες ή τα δεδομένα και οι ακμές λειτουργούν ως σύνδεσμος μεταξύ ενός ζεύγους κορυφών.
Τα γραφήματα μπορούν να είναι πολλαπλών τύπων, ανάλογα με τη θέση των κόμβων και των ακμών. Ακολουθούν ορισμένοι σημαντικοί τύποι γραφημάτων:
Σκηνοθετημένη Γράφημα
Οι ακμές του Κατευθυνόμενου Γραφήματος περιέχουν βέλη που υποδηλώνουν την κατεύθυνση. Το βέλος καθορίζει πού δείχνει ή τελειώνει η ακμή. Ακολουθεί ένα παράδειγμα του Κατευθυνόμενου Γραφήματος.
Σκηνοθετημένη Γράφημα
- Μπορούμε να πάμε από τον Κόμβο Α στον Δ.
- Ωστόσο, δεν μπορούμε να μεταβούμε από τον κόμβο D στον κόμβο A, καθώς η ακμή δείχνει από το A στο D.
- Καθώς το γράφημα δεν έχει βάρη, το ταξίδι από την κορυφή Α στο D θα κοστίσει το ίδιο με το ταξίδι από το D στο F.
Μη κατευθυνόμενο γράφημα
Ένα μη κατευθυνόμενο γράφημα περιέχει ακμές χωρίς δείκτες. Αυτό σημαίνει ότι μπορούμε να ταξιδέψουμε αντίστροφα μεταξύ δύο κορυφών. Ακολουθεί ένα απλό παράδειγμα μη κατευθυνόμενου γραφήματος.
Μη κατευθυνόμενο γράφημα
Στο παραπάνω γράφημα,
- Μπορούμε να μετακινηθούμε από το Α στο Β.
- Μπορούμε επίσης να μεταβούμε από το Β στο Α.
- Οι άκρες δεν περιέχουν οδηγίες.
Είναι ένα παράδειγμα μη κατευθυνόμενου γραφήματος που έχει πεπερασμένο αριθμό κορυφών και ακμών χωρίς βάρη.
Σταθμισμένο γράφημα
Ένα γράφημα που περιέχει βάρη ή κόστη στις άκρες ονομάζεται σταθμισμένο γράφημα. Η αριθμητική τιμή γενικά αντιπροσωπεύει το κόστος μετακίνησης από μια κορυφή σε μια άλλη. Τόσο τα κατευθυνόμενα όσο και τα μη κατευθυνόμενα γραφήματα μπορούν να έχουν βάρη στις άκρες τους. Ακολουθεί ένα παράδειγμα σταθμισμένου γραφήματος (Κατευθυνόμενου).
Σκηνοθετημένο γράφημα με βάρος
- Από το Α στο Β, υπάρχει μια άκρη και το βάρος είναι 5, πράγμα που σημαίνει ότι η μετακίνηση από το Α στο Β θα μας κοστίσει 5.
- Το Α δείχνει προς το Β, αλλά σε αυτό το Γράφημα, το Β δεν έχει άμεσο πλεονέκτημα έναντι του Α. Επομένως, δεν μπορούμε να ταξιδέψουμε από το Β στο Α.
- Ωστόσο, αν θέλουμε να μετακινηθούμε από το A στο F, υπάρχουν πολλαπλές διαδρομές. Οι διαδρομές είναι ADF και ABF. Το ADF θα κοστίσει (10+11) ή 21.
- Εδώ, η διαδρομή ABF θα κοστίσει (5+15) ή 20. Εδώ προσθέτουμε το βάρος κάθε ακμής στη διαδρομή.
Ακολουθεί ένα παράδειγμα μη κατευθυνόμενου γραφήματος με βάρη:
Μη κατευθυνόμενο γράφημα με βάρος
Εδώ, η άκρη έχει βάρος αλλά δεν έχει κατεύθυνση. Έτσι, σημαίνει ότι το ταξίδι από την κορυφή Α στην Δ θα κοστίζει 10 και το αντίστροφο.
Γράφημα διπλής κατεύθυνσης
Τα αμφίδρομα και τα μη κατευθυνόμενα γραφήματα έχουν μια κοινή ιδιότητα. Δηλαδή:
- Γενικά, ένα μη κατευθυνόμενο γράφημα μπορεί να έχει μία ακμή μεταξύ δύο κορυφών.
Για παράδειγμα:
- Εδώ, η μετακίνηση από το Α στο Δ ή το Δ στο Α θα κοστίσει 10.
- Σε ένα αμφίδρομο γράφημα, μπορούμε να έχουμε δύο ακμές μεταξύ δύο κορυφών.
Ακολουθεί ένα παράδειγμα:
Γράφημα διπλής κατεύθυνσης
Το ταξίδι από το Α στο D θα μας κοστίσει 17, αλλά το ταξίδι από το D στο A θα μας κοστίσει 12. Επομένως, δεν μπορούμε να αντιστοιχίσουμε δύο διαφορετικά βάρη εάν πρόκειται για μη κατευθυνόμενο γράφημα.
Άπειρο γράφημα
Το Γράφημα θα περιέχει έναν άπειρο αριθμό ακμών και κόμβων. Εάν ένα γράφημα είναι άπειρο και είναι επίσης ένα συνδεδεμένο γράφημα, τότε θα περιέχει και έναν άπειρο αριθμό ακμών. Εδώ, οι εκτεταμένες ακμές σημαίνουν ότι περισσότερες ακμές μπορεί να συνδέονται με αυτούς τους κόμβους μέσω ακμών. Ακολουθεί ένα παράδειγμα του άπειρου Γράφου:
Άπειρο γράφημα
Μηδενικό γράφημα
Ένα Μηδενικό Γράφημα περιέχει μόνο κόμβους ή κορυφές αλλά χωρίς ακμές. Αν δοθεί ένα Γράφημα G = (V, E), όπου V είναι κορυφές και E είναι ακμές, θα είναι μηδενικό αν ο αριθμός των ακμών E είναι μηδέν. Ακολουθεί ένα παράδειγμα Μηδενικού Γράφου:
Μηδενικό γράφημα
Ασήμαντο γράφημα
Μια δομή δεδομένων γραφήματος θεωρείται τετριμμένη εάν υπάρχει μόνο μία κορυφή ή κόμβος χωρίς ακμές. Ακολουθεί ένα παράδειγμα τετριμμένου γραφήματος:
Πολλαπλό γράφημα
Ένα γράφημα ονομάζεται πολυγράφημα όταν υπάρχουν πολλαπλές ακμές μεταξύ δύο κορυφών ή όταν η κορυφή έχει έναν βρόχο. Ο όρος «Βρόχος» στη Δομή Δεδομένων Γραφήματος σημαίνει μια ακμή που δείχνει στον ίδιο κόμβο ή κορυφή. Ένα πολυγράφημα μπορεί να είναι κατευθυνόμενο ή μη κατευθυνόμενο. Ακολουθεί ένα παράδειγμα Πολυγράφου:
Υπάρχουν δύο ακμές από το Β στο Α. Επιπλέον, η κορυφή Ε έχει έναν αυτο-βρόχο. Το παραπάνω Γράφημα είναι ένα κατευθυνόμενο γράφημα χωρίς βάρη στις ακμές.
Πλήρες γράφημα
Ένα γράφημα είναι πλήρες αν κάθε κορυφή έχει κατευθυνόμενες ή μη κατευθυνόμενες ακμές με όλες τις άλλες κορυφές. Ας υποθέσουμε ότι υπάρχει συνολικά V αριθμός κορυφών και κάθε κορυφή έχει ακριβώς V-1 ακμές. Τότε, αυτό το γράφημα θα ονομάζεται Πλήρες Γράφημα. Σε αυτόν τον τύπο γραφήματος, κάθε κορυφή συνδέεται με όλες τις άλλες κορυφές μέσω ακμών. Ακολουθεί ένα παράδειγμα πλήρους γραφήματος με πέντε κορυφές:
Μπορείτε να δείτε στην εικόνα ότι ο συνολικός αριθμός κόμβων είναι πέντε και όλοι οι κόμβοι έχουν ακριβώς τέσσερις ακμές.
Συνδεδεμένο γράφημα
Ένα γράφημα ονομάζεται Συνδεδεμένο γράφημα αν ξεκινούμε από έναν κόμβο ή κορυφή και μπορούμε να ταξιδέψουμε σε όλους τους κόμβους από τον αρχικό κόμβο. Για αυτό, θα πρέπει να υπάρχει τουλάχιστον μία ακμή μεταξύ κάθε ζεύγους κόμβων ή κορυφών. Ακολουθεί ένα παράδειγμα Συνδεδεμένου Γράφου:
Ακολουθεί μια εξήγηση του παραπάνω Συνδεδεμένου Γράφου:
- Υποθέτοντας ότι δεν υπάρχει ακμή μεταξύ C και F, δεν μπορούμε να ταξιδέψουμε από το A στο G. Ωστόσο, η ακμή C προς το F μας επιτρέπει να ταξιδέψουμε σε οποιονδήποτε κόμβο από έναν δεδομένο κόμβο.
- Ένα πλήρες Γράφημα είναι ένα Συνδεδεμένο Γράφημα επειδή μπορούμε να μετακινηθούμε από έναν κόμβο σε οποιονδήποτε άλλο κόμβο στο δεδομένο Γράφημα.
Κυκλικό Γράφημα
Ένα γράφημα λέγεται κυκλικό εάν υπάρχουν ένας ή περισσότεροι κύκλοι στο γράφημα. Ακολουθεί ένα παράδειγμα κυκλικού γραφήματος:
Εδώ, οι κορυφές A, B και C σχηματίζουν έναν κύκλο. Ένα γράφημα μπορεί να έχει πολλαπλούς κύκλους μέσα του.
Κατευθυνόμενο ακυκλικό γράφημα (DAG)
Ένα γράφημα ονομάζεται Κατευθυνόμενο Ακυκλικό Γράφημα ή DAG εάν δεν υπάρχουν κύκλοι μέσα σε ένα γράφημα. Το DAG είναι σημαντικό κατά την εκτέλεση της Τοπολογική ταξινόμηση ή την εύρεση της σειράς εκτέλεσης. Το DAG είναι επίσης σημαντικό για τη δημιουργία συστημάτων προγραμματισμού ή τη σάρωση εξαρτήσεων πόρων, κ.λπ. Ωστόσο, το παραπάνω Γράφημα δεν περιέχει κανέναν κύκλο μέσα. Ακολουθεί ένα απλό παράδειγμα ενός Κατευθυνόμενου Ακυκλικού Γράφου (DAG):
Γράφημα κύκλου
Ένα Γράφημα Κύκλου δεν είναι το ίδιο με το κυκλικό Γράφημα. Σε ένα Γράφημα Κύκλου, κάθε κόμβος θα έχει ακριβώς δύο συνδεδεμένες ακμές, που σημαίνει ότι κάθε κόμβος θα έχει ακριβώς δύο μοίρες. Ακολουθεί ένα παράδειγμα Γράφημα Κύκλου:
Διμερές γράφημα
Αυτά τα είδη Διαγράμματα είναι ειδικά είδη γραφημάτων όπου οι κορυφές αντιστοιχίζονται σε δύο σύνολα. Ένα διμερές γράφημα πρέπει να ακολουθεί τον κανόνα:
- Τα δύο σύνολα κορυφών θα πρέπει να είναι διακριτά, πράγμα που σημαίνει ότι όλες οι κορυφές πρέπει να χωριστούν σε δύο ομάδες ή σύνολα.
- Οι κορυφές του ίδιου συνόλου δεν πρέπει να σχηματίζουν ακμές.
Γράφημα Euler
Μια δομή δεδομένων γραφήματος θεωρείται γράφημα Euler εάν όλες οι κορυφές έχουν άρτιο βαθμό. Ο όρος βαθμός κορυφών σημαίνει τον αριθμό των ακμών που δείχνουν προς ή από μια συγκεκριμένη κορυφή. Ακολουθεί ένα παράδειγμα γραφήματος Euler:
Όλες οι κορυφές έχουν άρτιους βαθμούς. Οι κορυφές A, D, E και H έχουν δύο βαθμούς. Εδώ, ο κόμβος C έχει τέσσερις βαθμούς, που είναι άρτιος.
Γράφημα Hamilton
Ένα Γράφημα Χάμιλτον είναι ένα Συνδεδεμένο Γράφημα, όπου μπορείτε να επισκεφθείτε όλες τις κορυφές από μια δεδομένη κορυφή χωρίς να επισκεφθείτε ξανά τον ίδιο κόμβο ή να χρησιμοποιήσετε την ίδια ακμή. Αυτό το είδος Συνδεδεμένου Γράφου είναι γνωστό ως «Γράφημα Χάμιλτον». Η διαδρομή που επισκέπτεστε για να επαληθεύσετε εάν το δεδομένο Γράφημα είναι Γράφημα Χάμιλτον ή όχι είναι γνωστή ως Μονοπάτι Χάμιλτον. Ακολουθεί ένα απλό παράδειγμα γραφήματος ενός Χάμιλτον:
Σε αυτήν την εικόνα, μπορούμε να επισκεφτούμε όλες τις κορυφές από οποιονδήποτε κόμβο στο παραπάνω Γράφημα. Ένα από τα μονοπάτια μπορεί να είναι ADCHBEΕίναι επίσης δυνατό να βρεθεί ένας Κύκλος Χάμιλτον. Ένας Κύκλος Χάμιλτον ξεκινά και τελειώνει στην ίδια κορυφή. Έτσι, ο Κύκλος Χάμιλτον θα είναι ADCHBEA.
