Αναζήτηση κατά πλάτος
Εμφάνιση
Αναζήτηση κατά πλάτος είναι ένας αλγόριθμος για διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή γράφου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου (ή από κάποιο αυθαίρετο κόμβο του γραφήματος, που μερικές φορές αναφέρεται ως "κλειδί αναζήτησης του"[1]) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενου επιπέδου.
Ψευδοκώδικας
[Επεξεργασία | επεξεργασία κώδικα]Η αναζήτηση κατά πλάτος επιτυγχάνεται με χρήση μιας βοηθητική ουράς. Οι κόμβοι των κάθε επιπέδων του δέντρου εισάγωνται διαδοχικά στη βοηθητική ουρά. Ο κάτωθι επαναληπτικός αλγόριθμος διακρίνει δύο περιπτώσεις:
- Περίπτωση ρίζας: Η ουρά είναι αρχικά κενή, συνεπώς ο κόμβος της ρίζας πρόστειθεται στη βοητική ουρά.
- Γενική περίπτωση: Όσο η βοηθητική ουρά δεν είναι κενή, εξαγωγή και επεξεργασία του επόμενου κόμβου από την ουρά. Στη συνέχεια, εισαγωγή στη βοηθητική ουρά όλων τών κόμβων παιδιών του τρέχοντος κόμβου. Εάν ο τρέχων κόμβος είναι φύλλο, δεν εισάγεται τίποτα.
Αναφορές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ «Graph500 benchmark specification (supercomputer performance evaluation)». Graph500.org, 2010. Αρχειοθετήθηκε από το πρωτότυπο στις 26 Μαρτίου 2015. Ανακτήθηκε στις 7 Μαρτίου 2018.