Αναζήτηση κατά πλάτος

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Κινούμενο παράδειγμα αναζήτησης κατά πλάτος

Αναζήτηση κατά πλάτος είναι ένας αλγόριθμος για διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή γράφου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου (ή από κάποιο αυθαίρετο κόμβο του γραφήματος, που μερικές φορές αναφέρεται ως "κλειδί αναζήτησης του"[1]) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενου επίπεδο.

Ψευδοκώδικας[Επεξεργασία | επεξεργασία κώδικα]

Η αναζήτηση κατά πλάτος επιτυγχάνεται με χρήση μιας βοηθητική ουράς. Οι κόμβοι των κάθε επιπέδων του δέντρου εισάγωνται διαδοχικά στη βοηθητική ουρά. Ο κάτωθι επαναληπτικός αλγόριθμος διακρίνει δύο περιπτώσεις:

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

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]