Αναζήτηση κατά πλάτος: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Τυπογραφικό |
Διάσωση 1 πηγών και υποβολή 0 για αρχειοθέτηση.) #IABot (v2.0 |
||
| Γραμμή 1: | Γραμμή 1: | ||
[[Αρχείο:Animated_BFS.gif|μικρογραφία|187x187εσ|Κινούμενο παράδειγμα αναζήτησης κατά πλάτος]] |
[[Αρχείο: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>) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενου επίπεδο. |
'''Αναζήτηση κατά πλάτος '''είναι ένας [[αλγόριθμος]] για διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή γράφου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου (ή από κάποιο αυθαίρετο κόμβο του γραφήματος, που μερικές φορές αναφέρεται ως "κλειδί αναζήτησης του"<ref>{{Cite web|url=http://www.graph500.org/specifications#sec-5|title=Graph500 benchmark specification (supercomputer performance evaluation)|publisher=Graph500.org, 2010|accessdate=2018-03-07|archiveurl=https://web.archive.org/web/20150326055019/http://www.graph500.org/specifications#sec-5|archivedate=2015-03-26|url-status=dead}}</ref>) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενου επίπεδο. |
||
== Ψευδοκώδικας == |
== Ψευδοκώδικας == |
||
Έκδοση από την 15:14, 25 Σεπτεμβρίου 2019
Αναζήτηση κατά πλάτος είναι ένας αλγόριθμος για διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή γράφου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου (ή από κάποιο αυθαίρετο κόμβο του γραφήματος, που μερικές φορές αναφέρεται ως "κλειδί αναζήτησης του"[1]) και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του επόμενου επίπεδο.
Ψευδοκώδικας
Η αναζήτηση κατά πλάτος επιτυγχάνεται με χρήση μιας βοηθητική ουράς. Οι κόμβοι των κάθε επιπέδων του δέντρου εισάγωνται διαδοχικά στη βοηθητική ουρά. Ο κάτωθι επαναληπτικός αλγόριθμος διακρίνει δύο περιπτώσεις:
- Περίπτωση ρίζας: Η ουρά είναι αρχικά κενή, συνεπώς ο κόμβος της ρίζας πρόστειθεται στη βοητική ουρά.
- Γενική περίπτωση: Όσο η βοηθητική ουρά δεν είναι κενή, εξαγωγή και επεξεργασία του επόμενου κόμβου από την ουρά. Στη συνέχεια, εισαγωγή στη βοηθητική ουρά όλων τών κόμβων παιδιών του τρέχοντος κόμβου. Εάν ο τρέχων κόμβος είναι φύλλο, δεν εισάγεται τίποτα.
Αναφορές
- ↑ «Graph500 benchmark specification (supercomputer performance evaluation)». Graph500.org, 2010. Αρχειοθετήθηκε από το πρωτότυπο στις 26 Μαρτίου 2015. Ανακτήθηκε στις 7 Μαρτίου 2018.