Διαφορά μεταξύ των αναθεωρήσεων του «Αναζήτηση κατά πλάτος»

Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
μ
Τυπογραφικό
(Δημιουργήθηκε από μετάφραση της σελίδας "Breadth-first search")
 
μ (Τυπογραφικό)
[[Αρχείο:Animated_BFS.gif|μικρογραφία|187x187εσ|Κινούμενο παράδειγμα αναζήτησης κατά πλάτος]]
'''Αναζήτηση κατά πλάτος '''είναι ένας [[αλγόριθμος]] για τη διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή γράφου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου (ή από κάποιο αυθαίρετο κόμβο του γραφήματος, που μερικές φορές αναφέρεται ως "κλειδί αναζήτησης του"<ref>{{Cite web|url=http://www.graph500.org/specifications#sec-5|title=Graph500 benchmark specification (supercomputer performance evaluation)|publisher=Graph500.org, 2010}}</ref>) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενοεπόμενου επίπεδο.
 
 
 
== Ψευδοκώδικας ==
Η αναζήτηση κατά πλάτος επιτυγχάνεται με χρήση μιας βοηθητική ουράς. Οι κόμβοι των κάθε επιπέδων του δέντρου εισάγωγονταιεισάγωνται διαδοχικά στη βοηθητική ουρά. Ο κάτωθι επαναληπτικός αλγόριθμος διακρίνει δύο περιπτώσεις:
* '''Περίπτωση ρίζας''': Η ουρά είναι αρχικά κενή, συνεπώς ο κόμβος της ρίζας πρόστειθεται στη βοητική ουρά.
* '''Γενική περίπτωση''': Όσο η βοηθητική ουρά δεν είναι κενή, εξαγωγή και επεξεργασία του επόμενου κόμβου από την ουρά. Στη συνέχεια, εισαγωγή στη βοηθητική ουρά όλων τών κόμβων παιδιών του τρέχοντος κόμβου. Εάν ο τρέχων κόμβος είναι φύλλο, δεν εισάγεται τίποτα.
66

επεξεργασίες

Μενού πλοήγησης