Αλγόριθμος Πρώτης Αναζήτησης Εύρους (BFS) με EXAMPLE

Τι είναι ο αλγόριθμος BFS (Breadth-First Search);

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

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

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

Τι είναι οι διασχίσεις γραφήματος;

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

Η αρχιτεκτονική του αλγορίθμου BFS

1. Στα διάφορα επίπεδα των δεδομένων, μπορείτε να επισημάνετε οποιονδήποτε κόμβο ως αρχικό ή αρχικό κόμβο για να ξεκινήσει η διέλευση. Το BFS θα επισκεφθεί τον κόμβο και θα τον επισημάνει ως επισκέψιμο και θα τον τοποθετήσει στην ουρά.
2. Τώρα το BFS θα επισκεφθεί τους πλησιέστερους και τους μη επισκέψιμους κόμβους και θα τους σημαδέψει. Αυτές οι τιμές προστίθενται επίσης στην ουρά. Η ουρά λειτουργεί στο Μοντέλο FIFO.
3. Με παρόμοιο τρόπο, οι υπόλοιποι πλησιέστεροι και μη επισκέψιμοι κόμβοι στο γράφημα αναλύονται σημειωμένοι και προστίθενται στην ουρά. Αυτά τα στοιχεία διαγράφονται από την ουρά ως παραλαβή και εκτυπώνονται ως αποτέλεσμα.

Γιατί χρειαζόμαστε τον αλγόριθμο 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-First in First Out) δομή δεδομένων χρησιμοποιείται από την BFS.
• Σημειώνετε οποιονδήποτε κόμβο στο γράφημα ως ρίζα και ξεκινάτε να διασχίζετε τα δεδομένα από αυτόν.
• Το BFS διασχίζει όλους τους κόμβους στο γράφημα και συνεχίζει να τους αφήνει ως ολοκληρωμένους.
• Το BFS επισκέπτεται έναν παρακείμενο κόμβο χωρίς επίσκεψη, τον επισημαίνει ως ολοκληρωμένο και τον εισάγει σε μια ουρά.
• Αφαιρεί την προηγούμενη κορυφή από την ουρά σε περίπτωση που δεν βρεθεί γειτονική κορυφή.
• Ο αλγόριθμος BFS επαναλαμβάνεται έως ότου όλες οι κορυφές του γραφήματος διασχιστούν με επιτυχία και επισημανθούν ως ολοκληρωμένες.
• Δεν υπάρχουν βρόχοι που προκαλούνται από το BFS κατά τη διέλευση δεδομένων από οποιονδήποτε κόμβο.

Εφαρμογές αλγορίθμου BFS

Ας ρίξουμε μια ματιά σε μερικές από τις πραγματικές εφαρμογές όπου μια εφαρμογή αλγορίθμου BFS μπορεί να είναι εξαιρετικά αποτελεσματική.

• Μη σταθμισμένα γραφήματα: Ο αλγόριθμος BFS μπορεί εύκολα να δημιουργήσει τη συντομότερη διαδρομή και ένα ελάχιστο εκτεινόμενο δέντρο για να επισκεφθεί όλες τις κορυφές του γραφήματος στο συντομότερο δυνατό χρόνο με υψηλή ακρίβεια.
• Δίκτυα P2P: Το BFS μπορεί να εφαρμοστεί για να εντοπίσει όλους τους πλησιέστερους ή γειτονικούς κόμβους σε ένα δίκτυο peer to peer. Αυτό θα βρει τα απαιτούμενα δεδομένα πιο γρήγορα.
• Ανιχνευτές Ιστού: Οι μηχανές αναζήτησης ή οι ανιχνευτές ιστού μπορούν εύκολα να δημιουργήσουν πολλαπλά επίπεδα ευρετηρίων χρησιμοποιώντας BFS. Η υλοποίηση του BFS ξεκινά από την πηγή, που είναι η ιστοσελίδα, και στη συνέχεια επισκέπτεται όλους τους συνδέσμους από αυτήν την πηγή.
• Συστήματα πλοήγησης: Το BFS μπορεί να βοηθήσει στην εύρεση όλων των γειτονικών τοποθεσιών από την κύρια ή την τοποθεσία πηγής.
• Δικτυακή μετάδοση: Ένα μεταδιδόμενο πακέτο καθοδηγείται από τον αλγόριθμο BFS για να βρει και να φτάσει σε όλους τους κόμβους για τους οποίους έχει τη διεύθυνση.

Σύνοψη

• Η διέλευση γραφήματος είναι μια μοναδική διαδικασία που απαιτεί από τον αλγόριθμο να επισκέπτεται, να ελέγχει και/ή να ενημερώνει κάθε κόμβο που δεν έχει επισκεφτεί σε μια δομή που μοιάζει με δέντρο. Ο αλγόριθμος BFS λειτουργεί με παρόμοια αρχή.
• Ο αλγόριθμος είναι χρήσιμος για την ανάλυση των κόμβων σε ένα γράφημα και την κατασκευή της συντομότερης διαδρομής διέλευσης μέσω αυτών.
• Ο αλγόριθμος διασχίζει το γράφημα με τον μικρότερο αριθμό επαναλήψεων και το συντομότερο δυνατό χρόνο.
• Το BFS επιλέγει έναν μεμονωμένο κόμβο (αρχικό ή σημείο πηγής) σε ένα γράφημα και στη συνέχεια επισκέπτεται όλους τους κόμβους που βρίσκονται δίπλα στον επιλεγμένο κόμβο. Το BFS έχει πρόσβαση σε αυτούς τους κόμβους έναν προς έναν.
• Τα δεδομένα επίσκεψης και επισήμανσης τοποθετούνται σε μια ουρά από το BFS. Μια ουρά λειτουργεί με βάση την πρώτη έξοδο. Ως εκ τούτου, το στοιχείο που τοποθετείται πρώτα στο γράφημα διαγράφεται πρώτο και εκτυπώνεται ως αποτέλεσμα.
• Ο αλγόριθμος BFS δεν μπορεί ποτέ να παγιδευτεί σε έναν άπειρο βρόχο.
• Λόγω της υψηλής ακρίβειας και της στιβαρής υλοποίησης, το BFS χρησιμοποιείται σε πολλές πραγματικές λύσεις όπως δίκτυα P2P, ανιχνευτές Ιστού και δικτυακή μετάδοση.