Γράφημα εναντίον δέντρου
Το Γράφημα και δέντρο χρησιμοποιούνται σε δομές δεδομένων. Υπάρχουν σίγουρα κάποιες διαφορές μεταξύ του γραφήματος και του δέντρου. Ένα σύνολο κορυφών που έχουν δυαδική σχέση ονομάζεται γράφημα, ενώ το δέντρο είναι μια δομή δεδομένων που έχει ένα σύνολο κόμβων συνδεδεμένων μεταξύ τους.
Γράφημα
Ένα γράφημα είναι ένα σύνολο στοιχείων που συνδέονται με ακμές και κάθε στοιχείο είναι γνωστό ως κόμβος ή κορυφή. Με άλλα λόγια, ένα γράφημα μπορεί να οριστεί ως το σύνολο των κορυφών και υπάρχει μια δυαδική σχέση μεταξύ αυτών των κορυφών.
Στην υλοποίηση ενός γραφήματος, οι κόμβοι υλοποιούνται ως αντικείμενα ή δομές. Οι άκρες μπορούν να αναπαρασταθούν με διαφορετικούς τρόπους. Ένας από τους τρόπους είναι ότι κάθε κόμβος μπορεί να συσχετιστεί με έναν πίνακα προσπίπτοντων ακμών. Εάν οι πληροφορίες πρόκειται να αποθηκευτούν σε κόμβους και όχι σε ακμές, τότε οι πίνακες λειτουργούν ως δείκτες σε κόμβους και αντιπροσωπεύουν επίσης ακμές. Ένα από τα πλεονεκτήματα αυτής της προσέγγισης είναι ότι μπορούν να προστεθούν επιπλέον κόμβοι στο γράφημα. Οι υπάρχοντες κόμβοι μπορούν να συνδεθούν προσθέτοντας στοιχεία σε πίνακες. Υπάρχει όμως ένα μειονέκτημα γιατί απαιτείται χρόνος για να καθοριστεί αν υπάρχει ακμή μεταξύ των κόμβων.
Άλλος τρόπος για να γίνει αυτό είναι να διατηρήσετε έναν δισδιάστατο πίνακα ή πίνακα M που έχει Boolean τιμές. Η ύπαρξη ακμής από τον κόμβο i έως το j καθορίζεται από την καταχώρηση Mij. Ένα από τα πλεονεκτήματα αυτής της μεθόδου είναι να ανακαλύψετε εάν υπάρχει κάποια άκρη μεταξύ δύο κόμβων.
Δέντρο
Το Το δέντρο είναι επίσης μια δομή δεδομένων που χρησιμοποιείται στην επιστήμη των υπολογιστών. Είναι παρόμοιο με τη δομή του δέντρου και έχει ένα σύνολο κόμβων που συνδέονται μεταξύ τους.
Ένας κόμβος ενός δέντρου μπορεί να περιέχει μια συνθήκη ή μια τιμή. Μπορεί επίσης να είναι ένα δέντρο από μόνο του ή μπορεί να αντιπροσωπεύει μια ξεχωριστή δομή δεδομένων. Μηδέν ή περισσότεροι κόμβοι υπάρχουν σε μια δομή δεδομένων δέντρου. Εάν ένας κόμβος έχει παιδί, τότε ονομάζεται γονικός κόμβος αυτού του παιδιού. Μπορεί να υπάρχει το πολύ ένας γονέας ενός κόμβου. Η μεγαλύτερη καθοδική διαδρομή από τον κόμβο σε ένα φύλλο είναι το ύψος του κόμβου. Το βάθος του κόμβου αντιπροσωπεύεται από τη διαδρομή προς τη ρίζα του.
Σε ένα δέντρο, ο κορυφαίος κόμβος ονομάζεται κόμβος ρίζας. Ο ριζικός κόμβος δεν έχει γονείς καθώς είναι ο κορυφαίος. Από αυτόν τον κόμβο ξεκινούν όλες οι λειτουργίες δέντρου. Χρησιμοποιώντας συνδέσμους ή άκρες, μπορείτε να προσεγγίσετε άλλους κόμβους από τον ριζικό κόμβο. Οι κόμβοι στο χαμηλότερο επίπεδο ονομάζονται κόμβοι φύλλων και δεν έχουν παιδιά. Ο κόμβος που έχει αριθμό θυγατρικών κόμβων ονομάζεται εσωτερικός κόμβος ή εσωτερικός κόμβος.
Διαφορά μεταξύ γραφήματος και δέντρου:
• Ένα δέντρο μπορεί να περιγραφεί ως μια εξειδικευμένη περίπτωση γραφήματος χωρίς αυτοβρόχους και κυκλώματα.
• Δεν υπάρχουν βρόχοι σε ένα δέντρο, ενώ ένα γράφημα μπορεί να έχει βρόχους.
• Υπάρχουν τρία σύνολα σε ένα γράφημα, δηλαδή ακμές, κορυφές και ένα σύνολο που αντιπροσωπεύει τη σχέση τους, ενώ ένα δέντρο αποτελείται από κόμβους που συνδέονται μεταξύ τους. Αυτές οι συνδέσεις αναφέρονται ως άκρες.
• Στο δέντρο υπάρχουν πολλοί κανόνες που εξηγούν πώς μπορούν να συμβούν οι συνδέσεις των κόμβων, ενώ το γράφημα δεν έχει κανόνες που υπαγορεύουν τη σύνδεση μεταξύ των κόμβων.
