Αλγόριθμος Πρώτης Αναζήτησης Εύρους (BFS) με EXAMPLE
Σάρα Τσεν
⚡ Έξυπνη Σύνοψη
Η Αναζήτηση Πρώτα σε Πλάτος (BFS) είναι ένας αλγόριθμος που διασχίζει ένα γράφημα επίπεδο προς επίπεδο, επισκεπτόμενος όλους τους γείτονες ενός κόμβου πριν προχωρήσει σε βάθος. Χρησιμοποιεί μια ουρά FIFO και βρίσκει τη συντομότερη διαδρομή σε μη σταθμισμένα γράφημα χωρίς άπειρους βρόχους.
Τι είναι ο αλγόριθμος BFS (Breadth-First Search);
Η αναζήτηση κατά πλάτος (BFS) είναι ένας αλγόριθμος που χρησιμοποιείται για την απεικόνιση δεδομένων σε γραφήματα ή την αναζήτηση ενός δέντρου ή την διέλευση δομών. Η πλήρης μορφή της BFS είναι η αναζήτηση κατά πλάτος.
Ο αλγόριθμος επισκέπτεται αποτελεσματικά και επισημαίνει όλους τους βασικούς κόμβους σε ένα γράφημα με ακριβή τρόπο. Αυτός ο αλγόριθμος επιλέγει έναν μόνο κόμβο (αρχικό ή σημείο πηγής) σε ένα γράφημα και στη συνέχεια επισκέπτεται όλους τους κόμβους που βρίσκονται δίπλα στον επιλεγμένο κόμβο. Θυμηθείτε, το BFS έχει πρόσβαση σε αυτούς τους κόμβους έναν προς έναν.
Μόλις ο αλγόριθμος επισκεφθεί και σημειώσει τον αρχικό κόμβο, τότε μετακινείται προς τους πλησιέστερους μη επισκέψιμους κόμβους και τους αναλύει. Μετά την επίσκεψη, όλοι οι κόμβοι επισημαίνονται. Αυτές οι επαναλήψεις συνεχίζονται έως ότου γίνει επιτυχής επίσκεψη και επισήμανση όλων των κόμβων του γραφήματος.
Τι είναι οι διασχίσεις γραφήματος;
Η διέλευση γραφήματος είναι μια ευρέως χρησιμοποιούμενη μεθοδολογία για τον εντοπισμό της θέσης κορυφής στο γράφημα. Είναι ένας προηγμένος αλγόριθμος αναζήτησης που μπορεί να αναλύσει το γράφημα με ταχύτητα και ακρίβεια μαζί με τη σήμανση της ακολουθίας των κορυφών που επισκέφθηκες. Αυτή η διαδικασία σάς επιτρέπει να επισκέπτεστε γρήγορα κάθε κόμβο σε ένα γράφημα χωρίς να κλειδώνεστε σε έναν άπειρο βρόχο.
Η αρχιτεκτονική του αλγορίθμου BFS
- Στα διάφορα επίπεδα των δεδομένων, μπορείτε να επισημάνετε οποιονδήποτε κόμβο ως τον αρχικό ή αρχικό κόμβο για να ξεκινήσετε τη διέλευση. Το BFS θα επισκεφτεί τον κόμβο, θα τον επισημάνει ως επισκεπτόμενο και θα τον τοποθετήσει στην ουρά.
- Τώρα, το BFS θα επισκεφτεί τους πλησιέστερους και μη επισκεπτόμενους κόμβους και θα τους επισημάνει. Αυτές οι τιμές προστίθενται επίσης στην ουρά. Η ουρά λειτουργεί στο Μοντέλο FIFO.
- Με παρόμοιο τρόπο, οι υπόλοιποι πλησιέστεροι και μη επισκεπτόμενοι κόμβοι στο γράφημα αναλύονται, επισημαίνονται και προστίθενται στην ουρά. Αυτά τα στοιχεία διαγράφονται από την ουρά καθώς λαμβάνονται και εκτυπώνονται ως αποτέλεσμα.
Γιατί χρειαζόμαστε τον αλγόριθμο BFS;
Υπάρχουν πολλοί λόγοι για να χρησιμοποιήσετε τον αλγόριθμο BFS για την αναζήτηση στο σύνολο δεδομένων σας. Μερικές από τις πιο σημαντικές πτυχές που καθιστούν αυτόν τον αλγόριθμο την πρώτη σας επιλογή είναι:
- Το BFS είναι χρήσιμο για την ανάλυση των κόμβων σε ένα γράφημα και την κατασκευή της συντομότερης διαδρομής διέλευσης μέσω αυτών.
- Το BFS μπορεί να διασχίσει ένα γράφημα με τον μικρότερο αριθμό επαναλήψεων.
- Η αρχιτεκτονική του αλγορίθμου BFS είναι απλή και στιβαρή.
- Το αποτέλεσμα του αλγορίθμου BFS έχει υψηλό επίπεδο ακρίβειας σε σύγκριση με άλλους αλγόριθμους.
- Οι επαναλήψεις BFS είναι απρόσκοπτες και δεν υπάρχει πιθανότητα αυτός ο αλγόριθμος να εγκλωβιστεί σε ένα πρόβλημα απεριόριστου βρόχου.
Πώς λειτουργεί ο αλγόριθμος BFS;
Η διέλευση γραφήματος απαιτεί από τον αλγόριθμο να επισκέπτεται, να ελέγχει και/ή να ενημερώνει κάθε μεμονωμένο κόμβο που δεν έχει επισκεφτεί σε μια δομή που μοιάζει με δέντρο. Οι διασχίσεις γραφημάτων κατηγοριοποιούνται με βάση τη σειρά με την οποία επισκέπτονται τους κόμβους στο γράφημα.
Ο αλγόριθμος BFS ξεκινά τη λειτουργία από τον πρώτο ή τον αρχικό κόμβο σε ένα γράφημα και τον διασχίζει διεξοδικά. Μόλις διασχίσει επιτυχώς τον αρχικό κόμβο, τότε γίνεται επίσκεψη και επισήμανση της επόμενης μη διασχιζόμενης κορυφής στο γράφημα.
Επομένως, μπορούμε να πούμε ότι όλοι οι κόμβοι που γειτνιάζουν με την τρέχουσα κορυφή επισκέπτονται και διασχίζονται στην πρώτη επανάληψη. Χρησιμοποιείται μια απλή μεθοδολογία ουράς για την υλοποίηση της λειτουργίας ενός αλγορίθμου BFS, η οποία αποτελείται από τα ακόλουθα βήματα:
Βήμα 1)
Κάθε κορυφή ή κόμβος στο γράφημα είναι γνωστή. Για παράδειγμα, μπορείτε να επισημάνετε τον κόμβο ως V.
Βήμα 2)
Σε περίπτωση που δεν είναι δυνατή η πρόσβαση στην κορυφή V, τότε προσθέστε την κορυφή V στην ουρά BFS.
Βήμα 3)
Ξεκινήστε την αναζήτηση BFS και, μετά την ολοκλήρωσή της, επισημάνετε την κορυφή V ως επισκεπτόμενη.
Βήμα 4)
Η ουρά BFS εξακολουθεί να μην είναι κενή, επομένως αφαιρέστε την κορυφή V του γραφήματος από την ουρά.
Βήμα 5)
Ανακτήστε όλες τις υπόλοιπες κορυφές στο γράφημα που είναι γειτονικές της κορυφής V.
Βήμα 6)
Για κάθε γειτονική κορυφή, ας πούμε V1, σε περίπτωση που δεν έχει επισκεφθεί ακόμη, τότε προσθέστε την V1 στην ουρά BFS.
Βήμα 7)
Το BFS θα επισκεφτεί την έκδοση V1, θα την επισημάνει ως επισκεπτόμενη και θα τη διαγράψει από την ουρά.
Παράδειγμα αλγόριθμου BFS
Βήμα 1)
Έχετε ένα γράφημα επτά αριθμών που κυμαίνονται από το 0 έως το 6.
Βήμα 2)
Το 0 ή το μηδέν έχει επισημανθεί ως ριζικός κόμβος.
Βήμα 3)
Το 0 επισκέπτεται, επισημαίνεται και εισάγεται στη δομή δεδομένων ουράς.
Βήμα 4)
Οι υπόλοιποι γειτονικοί με 0 και μη επισκεπτόμενοι κόμβοι επισκέπτονται, σημειώνονται και εισάγονται στην ουρά.
Βήμα 5)
Οι επαναλήψεις διέλευσης επαναλαμβάνονται μέχρι να γίνει επίσκεψη σε όλους τους κόμβους.
Κανόνες αλγορίθμου BFS
Ακολουθούν σημαντικοί κανόνες για τη χρήση του αλγορίθμου BFS:
- Μια ουρά (FIFO – Πρώτος μέσα, πρώτος έξω) δομή δεδομένων χρησιμοποιείται από την BFS.
- Σημειώνετε οποιονδήποτε κόμβο στο γράφημα ως ρίζα και ξεκινάτε την επεξεργασία των δεδομένων από αυτόν.
- Το BFS διασχίζει όλους τους κόμβους στο γράφημα και συνεχίζει να μειώνεταιping τα ως ολοκληρωμένα.
- Το BFS επισκέπτεται έναν παρακείμενο κόμβο χωρίς επίσκεψη, τον επισημαίνει ως ολοκληρωμένο και τον εισάγει σε μια ουρά.
- Αφαιρεί την προηγούμενη κορυφή από την ουρά σε περίπτωση που δεν βρεθεί γειτονική κορυφή.
- Ο αλγόριθμος BFS επαναλαμβάνεται μέχρι να διασχιστούν με επιτυχία όλες οι κορυφές του γραφήματος και να επισημανθούν ως ολοκληρωμένες.
- Δεν υπάρχουν βρόχοι που προκαλούνται από το BFS κατά τη διέλευση δεδομένων από οποιονδήποτε κόμβο.
Εφαρμογές αλγορίθμου BFS
Ας ρίξουμε μια ματιά σε μερικές από τις πραγματικές εφαρμογές όπου μια εφαρμογή αλγορίθμου BFS μπορεί να είναι εξαιρετικά αποτελεσματική.
- Μη σταθμισμένα γραφήματα: Ο αλγόριθμος BFS μπορεί εύκολα να δημιουργήσει τη συντομότερη διαδρομή και ένα ελάχιστο δέντρο κάλυψης για να επισκεφτεί όλες τις κορυφές του γραφήματος στον συντομότερο δυνατό χρόνο με υψηλή ακρίβεια.
- Δίκτυα P2P: Το BFS μπορεί να εφαρμοστεί για τον εντοπισμό όλων των πλησιέστερων ή γειτονικών κόμβων σε ένα δίκτυο peer-to-peer. Αυτό θα βρει τα απαιτούμενα δεδομένα πιο γρήγορα.
- Ανιχνευτές Ιστού: Οι μηχανές αναζήτησης ή οι ανιχνευτές ιστού μπορούν εύκολα να δημιουργήσουν πολλαπλά επίπεδα ευρετηρίων χρησιμοποιώντας BFS. Η υλοποίηση του BFS ξεκινά από την πηγή, που είναι η ιστοσελίδα, και στη συνέχεια επισκέπτεται όλους τους συνδέσμους από αυτήν την πηγή.
- Συστήματα πλοήγησης: Το BFS μπορεί να βοηθήσει στην εύρεση όλων των γειτονικών τοποθεσιών από την κύρια ή την τοποθεσία πηγής.
- Δικτυακή μετάδοση: Ένα μεταδιδόμενο πακέτο καθοδηγείται από τον αλγόριθμο BFS για να βρει και να φτάσει σε όλους τους κόμβους για τους οποίους έχει τη διεύθυνση.
