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