Διαφορά μεταξύ γραφήματος και δέντρου

Graph vs. Tree

γράφημα και δέντρο χρησιμοποιούνται σε δομές δεδομένων. Υπάρχουν σίγουρα ορισμένες διαφορές μεταξύ του γραφήματος και του δέντρου. Ένα σύνολο κορυφών που έχουν μια δυαδική σχέση ονομάζεται γράφημα ενώ το δέντρο είναι μια δομή δεδομένων που έχει ένα σύνολο κόμβων συνδεδεμένων μεταξύ τους.

Γράφημα

Ένα γράφημα είναι ένα σύνολο στοιχείων που συνδέονται με ακμές και κάθε στοιχείο είναι γνωστό ως κόμβος ή κορυφή. Με άλλα λόγια, ένα γράφημα μπορεί να οριστεί ως το σύνολο των κορυφών και υπάρχει μια δυαδική σχέση μεταξύ αυτών των κορυφών.

Κατά την εφαρμογή ενός γραφήματος, οι κόμβοι υλοποιούνται ως αντικείμενα ή δομές. Οι άκρες μπορούν να εκπροσωπούνται με διάφορους τρόπους. Ένας από τους τρόπους είναι ότι κάθε κόμβος μπορεί να συσχετιστεί με μια συστοιχία περιθωρίων περιστατικών. Εάν οι πληροφορίες πρόκειται να αποθηκευτούν σε κόμβους και όχι σε άκρες, τότε οι πίνακες λειτουργούν ως δείκτες στους κόμβους και αντιπροσωπεύουν επίσης και άκρα. Ένα από τα πλεονεκτήματα αυτής της προσέγγισης είναι ότι πρόσθετοι κόμβοι μπορούν να προστεθούν στο γράφημα. Οι υπάρχοντες κόμβοι μπορούν να συνδεθούν προσθέτοντας στοιχεία σε συστοιχίες. Υπάρχει όμως ένα μειονέκτημα επειδή ο χρόνος είναι απαραίτητος για να καθοριστεί αν υπάρχει ένα άκρο μεταξύ των κόμβων.

Ένας άλλος τρόπος για να το κάνετε αυτό είναι να διατηρήσετε ένα δισδιάστατο πίνακα ή μήτρα M που έχει τιμές Boolean. Η ύπαρξη άκρου από τον κόμβο i έως το j καθορίζεται από την καταχώρηση Mij. Ένα από τα πλεονεκτήματα αυτής της μεθόδου είναι να διαπιστώσετε εάν υπάρχει κάποια άκρη μεταξύ δύο κόμβων.

Το δέντρο

είναι επίσης μια δομή δεδομένων που χρησιμοποιείται στην επιστήμη των υπολογιστών. Είναι παρόμοιο με τη δομή του δέντρου και έχει ένα σύνολο κόμβων που συνδέονται μεταξύ τους.

Ένας κόμβος ενός δέντρου μπορεί να περιέχει μια συνθήκη ή μια τιμή. Μπορεί επίσης να είναι δικό του δέντρο ή μπορεί να αντιπροσωπεύει ξεχωριστή δομή δεδομένων. Υπάρχουν μηδενικοί ή περισσότεροι κόμβοι σε μια δομή δεδομένων δέντρων. Αν ένας κόμβος έχει ένα παιδί τότε ονομάζεται γονικός κόμβος αυτού του παιδιού. Μπορεί να υπάρχει το πολύ ένας γονέας ενός κόμβου. Η μεγαλύτερη προς τα κάτω διαδρομή από τον κόμβο σε ένα φύλλο είναι το ύψος του κόμβου. Το βάθος του κόμβου αντιπροσωπεύεται από τη διαδρομή προς τη ρίζα του.

Σε ένα δέντρο, ο κορυφαίος κόμβος ονομάζεται κόμβος ρίζας. Ο κόμβος ρίζας δεν έχει γονείς, καθώς είναι ο κορυφαίος περισσότερος. Από αυτόν τον κόμβο, ξεκινούν όλες οι εργασίες των δέντρων. Χρησιμοποιώντας συνδέσμους ή ακμές, μπορούν να προσεγγιστούν άλλοι κόμβοι από τον κόμβο ρίζας. Οι κόμβοι του κατώτατου επιπέδου ονομάζονται κόμβοι φύλλων και δεν έχουν παιδιά. Ο κόμβος που έχει αριθμό παιδικών κόμβων ονομάζεται εσωτερικός κόμβος ή εσωτερικός κόμβος.

Διαφορά μεταξύ γραφήματος και δέντρου: • Ένα δέντρο μπορεί να περιγραφεί ως εξειδικευμένη περίπτωση γραφήματος χωρίς αυτοβυθίσματα και κυκλώματα. • Δεν υπάρχουν βρόχοι σε ένα δέντρο ενώ ένα γράφημα μπορεί να έχει βρόχους. • Υπάρχουν τρία σύνολα σε ένα γράφημα i. μι. άκρες, κορυφές και ένα σύνολο που αντιπροσωπεύει τη σχέση τους, ενώ ένα δέντρο αποτελείται από κόμβους που είναι συνδεδεμένοι μεταξύ τους.Αυτές οι συνδέσεις αναφέρονται ως άκρα. • Στο δέντρο υπάρχουν πολλοί κανόνες που εξηγούν πώς μπορούν να γίνουν συνδέσεις κόμβων ενώ το γράφημα δεν έχει κανόνες που υπαγορεύουν τη σύνδεση μεταξύ των κόμβων.