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

Αλγόριθμοι των Τραβερσών Δέντρων

Οι πιο κοινές μέθοδοι είναι η σειρά, η προ-παραγγελία, και η μετά-παραγγελία διατομή. Κάθε εξυπηρετεί διαφορετικούς σκοπούς και ακολουθεί μια μοναδική ακολουθία επίσκεψης.

Εσωστρεφής εντολή

Σε σειρά traversal επισκέπτεται το αριστερό υποδέντρο, το τρέχον κόμβο, τότε το δεξί υποδέντρο. Χρησιμοποιείται συχνά για την ανάκτηση δεδομένων σε ταξινομημένη σειρά από δυαδικά δέντρα αναζήτησης.

Παράδειγμα: Για ένα δυαδικό δέντρο με κόμβους 4, 2, 5, 1, 3, η εν σειρά διατομή είναι 1, 2, 3, 4, 5.

Προδιατακτικό

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

Παράδειγμα: Χρησιμοποιώντας το ίδιο δέντρο, η ακολουθία προ-παραγγελίας είναι 4, 2, 1, 3, 5.

Μεταδιαταγή Traversal

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

Παράδειγμα: Για το ίδιο δέντρο, η ακολουθία μετά την παραγγελία είναι 1, 3, 2, 5, 4.

Γράφημα Τραβερσικοί αλγόριθμοι

Οι δύο κύριες μέθοδοι είναι Breadth-First Search (BFS) και Depth-First Search (DFS). Χρησιμοποιούνται στην ανάλυση δικτύου, στην αναζήτηση διαδρομής και πολλά άλλα.

Ψύξη σε πλάτος (BFS)

Η BFS εξερευνά το επίπεδο των γειτόνων ανά επίπεδο, ξεκινώντας από έναν πηγαίο κόμβο. Χρησιμοποιεί μια ουρά για να παρακολουθεί τους κόμβους για να επισκεφθεί το επόμενο.

Παράδειγμα: Ξεκινώντας από τον κόμβο Α σε ένα γράφημα, η BFS επισκέπτεται κόμβους κατά σειρά: A, B, C, D, E, με βάση την εγγύτητα τους.

Πρώτη έρευνα βάθους (DFS)

Η DFS εξερευνά όσο το δυνατόν περισσότερο σε κάθε κλάδο πριν από την οπισθοδρόμηση. Χρησιμοποιεί μια στοίβα ή την επανάληψη για να διαχειριστεί την εγκάρσια.

Παράδειγμα: Ξεκινώντας από τον κόμβο Α, η DFS μπορεί να επισκεφθεί κόμβους κατά σειρά: A, B, D, E, C.