BFS — Επεξήγηση του αλγορίθμου αναζήτησης κατά πλάτος

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

Αυτή η σειρά επίπεδο προς επίπεδο είναι η βασική ιδέα. Αν ο γράφος είναι μη σταθμισμένος, ή κάθε ακμή έχει το ίδιο κόστος, τότε το BFS δίνει επίσης το μήκος της συντομότερης διαδρομής από τον αρχικό κόμβο προς κάθε προσβάσιμο κόμβο.

Τι κάνει η αναζήτηση κατά πλάτος

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

Το συνηθισμένο μοτίβο είναι:

• σημείωσε τον αρχικό κόμβο ως επισκεφθέντα
• βάλε τον στην ουρά
• αφαίρεσε τον μπροστινό κόμβο
• πρόσθεσε κάθε μη επισκεφθέντα γείτονα στο πίσω μέρος της ουράς
• επανάλαβε μέχρι να αδειάσει η ουρά

Αν αποθηκεύεις επίσης τον γονέα κάθε κόμβου, μπορείς να ανακατασκευάσεις μία συντομότερη διαδρομή αφού ολοκληρωθεί η αναζήτηση.

Γιατί η ουρά δημιουργεί επίπεδα

Έστω ότι ο κόμβος $A$ είναι η αρχή. Οι άμεσοι γείτονές του έχουν απόσταση $1$ από το $A$, οπότε μπαίνουν πρώτοι στην ουρά. Μόνο αφού επεξεργαστούν αυτοί οι κόμβοι, μπαίνουν οι μη επισκεφθέντες γείτονές τους, πράγμα που σημαίνει ότι το επόμενο κύμα έχει απόσταση $2$.

Γι’ αυτό το BFS ομαδοποιεί φυσικά τους κόμβους ανάλογα με την απόστασή τους από την αρχή. Δεν εκτιμά ποια διαδρομή είναι σύντομη. Η ουρά αναγκάζει την αναζήτηση να ολοκληρώσει όλες τις διαδρομές με λιγότερες ακμές πριν εξετάσει μεγαλύτερες.

Παράδειγμα BFS: εύρεση της συντομότερης διαδρομής με βάση τον αριθμό ακμών

Χρησιμοποίησε αυτόν τον γράφο:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Ξεκίνα από το $A$. Η ουρά αλλάζει ως εξής:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Να τι σημαίνει αυτό:

Πρώτα επεξεργαζόμαστε το $A$ και μετά προσθέτουμε τα $B$ και $C$. Στη συνέχεια επεξεργαζόμαστε το $B$ και μετά το $C$, οπότε προστίθενται τα $D$ και $E$. Έπειτα επεξεργαζόμαστε τα $D$ και $E$, και έτσι φτάνουμε στο $F$.

Άρα η σειρά επίσκεψης του BFS είναι:

$$A,\ B,\ C,\ D,\ E,\ F$$

Οι αποστάσεις από το $A$ είναι:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Αυτό δείχνει το βασικό όφελος. Το BFS φτάνει στο $F$ σε απόσταση $3$, άρα η συντομότερη διαδρομή από το $A$ στο $F$ χρησιμοποιεί $3$ ακμές. Μία συντομότερη διαδρομή είναι η $A \to B \to D \to F$. Μια άλλη είναι η $A \to C \to E \to F$.

Συνηθισμένα λάθη στο BFS

Η υπόθεση ότι το BFS βρίσκει πάντα τη φθηνότερη διαδρομή

Αυτό ισχύει μόνο όταν κάθε ακμή έχει το ίδιο κόστος ή όταν ο γράφος θεωρείται μη σταθμισμένος. Αν οι ακμές έχουν διαφορετικά βάρη, το BFS μπορεί να βρει μια διαδρομή με λιγότερες ακμές αλλά μεγαλύτερο συνολικό κόστος.

Καθυστερημένη σήμανση ενός κόμβου

Στο τυπικό BFS, ένας κόμβος συνήθως σημειώνεται ως επισκεφθείς όταν μπαίνει στην ουρά, όχι όταν αφαιρείται αργότερα. Αυτό αποτρέπει την προσθήκη του ίδιου κόμβου στην ουρά πολλές φορές.

Σύγχυση μεταξύ BFS και DFS

Το BFS εξερευνά κατά επίπεδα. Η αναζήτηση σε βάθος, ή DFS, συνεχίζει σε έναν κλάδο πριν επιστρέψει πίσω. Οι δύο αλγόριθμοι απαντούν καλά σε διαφορετικά είδη ερωτήσεων.

Το ότι η σειρά μπορεί να εξαρτάται από τη σειρά των γειτόνων

Η ακριβής σειρά επίσκεψης μέσα στο ίδιο επίπεδο μπορεί να αλλάξει ανάλογα με το πώς παρατίθενται οι γείτονες. Οι εγγυήσεις για τις αποστάσεις εξακολουθούν να ισχύουν, αλλά η σειρά διάσχισης μπορεί να διαφέρει.

Πότε χρησιμοποιείται η αναζήτηση κατά πλάτος

Το BFS είναι χρήσιμο όταν σε ενδιαφέρει η προσβασιμότητα, η διάσχιση κατά επίπεδα σε δέντρα ή τα μήκη συντομότερων διαδρομών που μετρώνται με αριθμό ακμών.

Εμφανίζεται επίσης σε προβλήματα χώρου καταστάσεων όπου κάθε κίνηση έχει το ίδιο κόστος. Σε αυτή την περίπτωση, το BFS είναι συχνά ο πιο καθαρός τρόπος για να βρεθεί ο ελάχιστος αριθμός κινήσεων.

Ένας απλός τρόπος να θυμάσαι το BFS

Σκέψου το BFS σαν ένα κύμα που απλώνεται προς τα έξω από τον αρχικό κόμβο. Κάθε βήμα του κύματος προσθέτει άλλη μία ακμή απόστασης.

Για να δοκιμάσεις τη δική σου εκδοχή, σχεδίασε έναν μικρό γράφο, διάλεξε έναν αρχικό κόμβο και γράψε την ουρά μετά από κάθε βήμα. Αν θέλεις ένα επόμενο βήμα, λύσε ένα παρόμοιο πρόβλημα διάσχισης γράφου και έλεγξε αν ο ισχυρισμός για τη συντομότερη διαδρομή εξακολουθεί να ισχύει όταν ο γράφος είναι σταθμισμένος.