Τι είναι ο αλγόριθμος BFS (Breadth-First Search);
Breadth-first search (BFS) είναι ένας αλγόριθμος που χρησιμοποιείται για τη γραφική παράσταση δεδομένων ή την αναζήτηση δέντρων ή διασχίζοντας δομές. Η πλήρης μορφή του BFS είναι η αναζήτηση πρώτου εύρους.
Ο αλγόριθμος επισκέπτεται και επισημαίνει αποτελεσματικά όλους τους βασικούς κόμβους σε ένα γράφημα με ακριβή τρόπο. Αυτός ο αλγόριθμος επιλέγει έναν μόνο κόμβο (αρχικό ή σημείο προέλευσης) σε ένα γράφημα και στη συνέχεια επισκέπτεται όλους τους κόμβους δίπλα στον επιλεγμένο κόμβο. Θυμηθείτε, το BFS αποκτά πρόσβαση σε αυτούς τους κόμβους ένα προς ένα.
Μόλις ο αλγόριθμος επισκέπτεται και επισημαίνει τον αρχικό κόμβο, τότε μετακινείται προς τους πλησιέστερους μη επισκέψιμους κόμβους και τους αναλύει. Μετά την επίσκεψη, όλοι οι κόμβοι επισημαίνονται. Αυτές οι επαναλήψεις συνεχίζονται έως ότου όλοι οι κόμβοι του γραφήματος έχουν επισκεφτεί και επισημανθεί με επιτυχία.
Σε αυτό το σεμινάριο Αλγόριθμου, θα μάθετε:
- Τι είναι ο αλγόριθμος BFS (Breadth-First Search);
- Τι είναι η διασταύρωση γραφήματος;
- Η αρχιτεκτονική του αλγορίθμου BFS
- Γιατί χρειαζόμαστε τον αλγόριθμο BFS;
- Πώς λειτουργεί ο αλγόριθμος BFS;
- Παράδειγμα Αλγόριθμος 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-First in First Out) χρησιμοποιείται από το BFS.
- Σημειώνετε οποιονδήποτε κόμβο στο γράφημα ως ρίζα και αρχίζετε να διασχίζετε τα δεδομένα από αυτό.
- Το BFS διασχίζει όλους τους κόμβους στο γράφημα και συνεχίζει να τους ρίχνει ως ολοκληρωμένος.
- Το BFS επισκέπτεται έναν παρακείμενο κόμβο που δεν έχει ελεγχθεί, τον επισημαίνει ως ολοκληρωμένο και τον εισάγει σε μια ουρά.
- Αφαιρεί την προηγούμενη κορυφή από την ουρά σε περίπτωση που δεν βρεθεί γειτονική κορυφή.
- Ο αλγόριθμος BFS επαναλαμβάνεται έως ότου όλες οι κορυφές στο γράφημα διασχίζονται επιτυχώς και επισημαίνονται ως ολοκληρωμένες.
- Δεν υπάρχουν βρόχοι που προκαλούνται από το BFS κατά τη διέλευση δεδομένων από οποιονδήποτε κόμβο.
Εφαρμογές του αλγορίθμου BFS
Ας ρίξουμε μια ματιά σε μερικές από τις πραγματικές εφαρμογές όπου η εφαρμογή αλγορίθμου BFS μπορεί να είναι εξαιρετικά αποτελεσματική.
- Μη σταθμισμένα γραφήματα: Ο αλγόριθμος BFS μπορεί εύκολα να δημιουργήσει τη συντομότερη διαδρομή και ένα ελάχιστο δέντρο έκτασης για να επισκεφτεί όλες τις κορυφές του γραφήματος στο συντομότερο δυνατό χρόνο με υψηλή ακρίβεια.
- Δίκτυα P2P: Το BFS μπορεί να εφαρμοστεί για να εντοπίσει όλους τους πλησιέστερους ή γειτονικούς κόμβους σε δίκτυο peer to peer. Αυτό θα βρει τα απαιτούμενα δεδομένα πιο γρήγορα.
- Web Crawlers: Οι μηχανές αναζήτησης ή οι ανιχνευτές ιστού μπορούν εύκολα να δημιουργήσουν πολλαπλά επίπεδα ευρετηρίων χρησιμοποιώντας το BFS. Η εφαρμογή BFS ξεκινά από την πηγή, η οποία είναι η ιστοσελίδα, και στη συνέχεια επισκέπτεται όλους τους συνδέσμους από αυτήν την πηγή.
- Συστήματα πλοήγησης: Το BFS μπορεί να σας βοηθήσει να βρείτε όλες τις γειτονικές τοποθεσίες από την κύρια ή την τοποθεσία προέλευσης.
- Δίκτυο μετάδοσης: Ένα πακέτο εκπομπής καθοδηγείται από τον αλγόριθμο BFS για να βρει και να φτάσει σε όλους τους κόμβους για τους οποίους έχει τη διεύθυνση.
Περίληψη
- Η διασταύρωση γραφημάτων είναι μια μοναδική διαδικασία που απαιτεί τον αλγόριθμο να επισκέπτεται, να ελέγχει και / ή να ενημερώνει κάθε κόμβο που δεν έχει επισκεφθεί σε μια δομή που μοιάζει με δέντρο. Ο αλγόριθμος BFS λειτουργεί με παρόμοια αρχή.
- Ο αλγόριθμος είναι χρήσιμος για την ανάλυση των κόμβων σε ένα γράφημα και την κατασκευή της συντομότερης διαδρομής που διασχίζει.
- Ο αλγόριθμος διασχίζει το γράφημα με τον μικρότερο αριθμό επαναλήψεων και το συντομότερο δυνατό χρόνο.
- Το BFS επιλέγει έναν μόνο κόμβο (αρχικό ή σημείο προέλευσης) σε ένα γράφημα και στη συνέχεια επισκέπτεται όλους τους κόμβους που γειτνιάζουν με τον επιλεγμένο κόμβο. Το BFS αποκτά πρόσβαση σε αυτούς τους κόμβους ένα προς ένα.
- Τα δεδομένα που επισκέφτηκαν και επισημάνθηκαν τοποθετούνται σε ουρά από την BFS. Η ουρά λειτουργεί με βάση την πρώτη στην πρώτη έξοδο. Ως εκ τούτου, το στοιχείο που τοποθετείται πρώτα στο γράφημα διαγράφεται πρώτα και εκτυπώνεται ως αποτέλεσμα.
- Ο αλγόριθμος BFS δεν μπορεί ποτέ να παγιδευτεί σε έναν άπειρο βρόχο.
- Λόγω της υψηλής ακρίβειας και της ισχυρής εφαρμογής, το BFS χρησιμοποιείται σε πολλές πραγματικές λύσεις όπως δίκτυα P2P, Web Crawlers και Network Broadcasting.