Τι είναι το BFS;
Το BFS είναι ένας αλγόριθμος που χρησιμοποιείται για τη γραφική παράσταση δεδομένων ή την αναζήτηση δέντρων ή διασχίζοντας δομές. Ο αλγόριθμος επισκέπτεται και επισημαίνει αποτελεσματικά όλους τους βασικούς κόμβους σε ένα γράφημα με ακριβή τρόπο.
Αυτός ο αλγόριθμος επιλέγει έναν μόνο κόμβο (αρχικό ή σημείο προέλευσης) σε ένα γράφημα και στη συνέχεια επισκέπτεται όλους τους κόμβους δίπλα στον επιλεγμένο κόμβο. Μόλις ο αλγόριθμος επισκέπτεται και επισημαίνει τον αρχικό κόμβο, τότε μετακινείται προς τους πλησιέστερους μη επισκέψιμους κόμβους και τους αναλύει.
Μετά την επίσκεψη, όλοι οι κόμβοι επισημαίνονται. Αυτές οι επαναλήψεις συνεχίζονται έως ότου όλοι οι κόμβοι του γραφήματος έχουν επισκεφτεί και επισημανθεί με επιτυχία. Η πλήρης μορφή του BFS είναι η αναζήτηση πρώτου εύρους.
Σε αυτό το BSF Vs. DFS Binary tree tutorial, θα μάθετε:
- Τι είναι το BFS;
- Τι είναι το DFS;
- Παράδειγμα BFS
- Παράδειγμα DFS
- Διαφορά μεταξύ BFS και DFS Binary Tree
- Εφαρμογές του BFS
- Εφαρμογές του DFS
Τι είναι το DFS;
Το DFS είναι ένας αλγόριθμος για την εύρεση ή διέλευση γραφημάτων ή δέντρων σε κατεύθυνση βάθους. Η εκτέλεση του αλγορίθμου ξεκινά στον ριζικό κόμβο και εξερευνά κάθε κλάδο πριν από το backtracking. Χρησιμοποιεί μια δομή δεδομένων στοίβας για να θυμάται, να πάρει την επόμενη κορυφή και για να ξεκινήσει μια αναζήτηση, όποτε εμφανίζεται αδιέξοδο σε οποιαδήποτε επανάληψη. Η πλήρης μορφή του DFS είναι η πρώτη αναζήτηση βάθους.
Παράδειγμα BFS
Στο ακόλουθο παράδειγμα DFS, χρησιμοποιήσαμε γράφημα με 6 κορυφές.
Παράδειγμα BFS
Βήμα 1)
Έχετε ένα γράφημα επτά αριθμών που κυμαίνονται από 0 - 6.
Βήμα 2)
0 ή μηδέν έχει επισημανθεί ως ριζικός κόμβος.
Βήμα 3)
0 επισκέπτεται, επισημαίνεται και εισάγεται στη δομή δεδομένων ουράς.
Βήμα 4)
Οι υπόλοιποι 0 γειτονικοί και μη επισκέψιμοι κόμβοι επισκέπτονται, επισημαίνονται και εισάγονται στην ουρά.
Βήμα 5)
Οι διασταυρούμενες επαναλήψεις επαναλαμβάνονται έως ότου επισκεφθούν όλους τους κόμβους.
Παράδειγμα DFS
Στο ακόλουθο παράδειγμα του DFS, χρησιμοποιήσαμε ένα μη κατευθυνόμενο γράφημα με 5 κορυφές.
Βήμα 1)
Ξεκινήσαμε από την κορυφή 0. Ο αλγόριθμος ξεκινά τοποθετώντας τον στη λίστα επισκέψεων και τοποθετώντας ταυτόχρονα όλες τις γειτονικές κορυφές του στη δομή δεδομένων που ονομάζεται στοίβα.
Βήμα 2)
Θα επισκεφθείτε το στοιχείο, το οποίο βρίσκεται στην κορυφή της στοίβας, για παράδειγμα, 1 και θα μεταβείτε στους γειτονικούς κόμβους του. Είναι επειδή το 0 έχει ήδη επισκεφτεί. Επομένως, επισκέπτουμε την κορυφή 2.
Βήμα 3)
Το Vertex 2 έχει μια μη επισκέψιμη κοντινή κορυφή στο 4. Επομένως, το προσθέτουμε στη στοίβα και το επισκέπτουμε.
Βήμα 4)
Τέλος, θα επισκεφθούμε την τελευταία κορυφή 3, δεν έχει κανένα μη διενεργούμενο διπλανό κόμβο. Ολοκληρώσαμε τη διασταύρωση του γραφήματος χρησιμοποιώντας τον αλγόριθμο DFS.
Διαφορά μεταξύ BFS και DFS Binary Tree
| BFS | DFS |
| Το BFS βρίσκει τη συντομότερη διαδρομή προς τον προορισμό. | Το DFS πηγαίνει στο κάτω μέρος ενός δευτερεύοντος δέντρου και μετά ακολουθεί. |
| Η πλήρης μορφή του BFS είναι Breadth-First Search. | Η πλήρης μορφή του DFS είναι Depth First Search. |
| Χρησιμοποιεί μια ουρά για να παρακολουθεί την επόμενη τοποθεσία για επίσκεψη. | Χρησιμοποιεί μια στοίβα για να παρακολουθεί την επόμενη τοποθεσία για επίσκεψη. |
| Το BFS διασχίζει ανάλογα με το επίπεδο του δέντρου. | Το DFS διασχίζει ανάλογα με το βάθος του δέντρου. |
| Εφαρμόζεται χρησιμοποιώντας τη λίστα FIFO. | Εφαρμόζεται χρησιμοποιώντας τη λίστα LIFO. |
| Απαιτεί περισσότερη μνήμη σε σύγκριση με το DFS. | Απαιτεί λιγότερη μνήμη σε σύγκριση με το BFS. |
| Αυτός ο αλγόριθμος δίνει τη λύση της ρηχότερης διαδρομής. | Αυτός ο αλγόριθμος δεν εγγυάται την πιο ρηχή λύση. |
| Δεν υπάρχει ανάγκη υποτροπής στο BFS. | Υπάρχει ανάγκη για backtracking στο DFS. |
| Δεν μπορείτε ποτέ να παγιδευτείτε σε πεπερασμένους βρόχους. | Μπορείτε να παγιδευτείτε σε άπειρους βρόχους. |
| Εάν δεν βρείτε κανένα στόχο, ίσως χρειαστεί να επεκτείνετε πολλούς κόμβους προτού βρεθεί η λύση. | Εάν δεν βρείτε κανένα στόχο, ενδέχεται να συμβεί η υποτροπή του κόμβου φύλλων. |
Εφαρμογές του BFS
Εδώ είναι οι Εφαρμογές του BFS:
Μη σταθμισμένα γραφήματα:
Ο αλγόριθμος BFS μπορεί εύκολα να δημιουργήσει τη συντομότερη διαδρομή και ένα ελάχιστο δέντρο έκτασης για να επισκεφτεί όλες τις κορυφές του γραφήματος στο συντομότερο δυνατό χρόνο με υψηλή ακρίβεια.
Δίκτυα P2P:
Το BFS μπορεί να εφαρμοστεί για να εντοπίσει όλους τους πλησιέστερους ή γειτονικούς κόμβους σε δίκτυο peer to peer. Αυτό θα βρει τα απαιτούμενα δεδομένα πιο γρήγορα.
Ανιχνευτές ιστού:
Οι μηχανές αναζήτησης ή οι ανιχνευτές ιστού μπορούν εύκολα να δημιουργήσουν πολλαπλά επίπεδα ευρετηρίων χρησιμοποιώντας BFS. Η εφαρμογή BFS ξεκινά από την πηγή, η οποία είναι η ιστοσελίδα, και στη συνέχεια επισκέπτεται όλους τους συνδέσμους από αυτήν την πηγή.
Εκπομπή δικτύου:
Ένα μεταδομένο πακέτο καθοδηγείται από τον αλγόριθμο BFS για να βρει και να φτάσει σε όλους τους κόμβους στους οποίους έχει τη διεύθυνση.
Εφαρμογές του DFS
Ακολουθούν σημαντικές εφαρμογές του DFS:
Σταθμισμένο γράφημα:
Σε ένα σταθμισμένο γράφημα, το γράφημα DFS traversal δημιουργεί το μικρότερο δέντρο διαδρομής και το ελάχιστο δέντρο έκτασης.
Ανίχνευση κύκλου σε γράφημα:
Ένα γράφημα έχει έναν κύκλο εάν βρήκαμε ένα πίσω άκρο κατά τη διάρκεια του DFS. Επομένως, πρέπει να εκτελέσουμε το DFS για το γράφημα και να επαληθεύσουμε για τα πίσω άκρα.
Εύρεση διαδρομής:
Μπορούμε να ειδικευθούμε στον αλγόριθμο DFS για αναζήτηση μιας διαδρομής μεταξύ δύο κορυφών.
Τοπολογική ταξινόμηση:
Χρησιμοποιείται κυρίως για τον προγραμματισμό εργασιών από τις δεδομένες εξαρτήσεις μεταξύ της ομάδας εργασιών. Στην επιστήμη των υπολογιστών, χρησιμοποιείται στον προγραμματισμό εντολών, στη σειριοποίηση δεδομένων, στη λογική σύνθεση, στον καθορισμό της σειράς των εργασιών σύνταξης.
Αναζήτηση ισχυρά συνδεδεμένων στοιχείων ενός γραφήματος:
Χρησιμοποιήθηκε στο γράφημα DFS όταν υπάρχει μια διαδρομή από κάθε κορυφή του γραφήματος προς άλλες υπόλοιπες κορυφές.
Επίλυση παζλ με μία μόνο λύση:
Ο αλγόριθμος DFS μπορεί εύκολα να προσαρμοστεί για να αναζητήσει όλες τις λύσεις σε ένα λαβύρινθο συμπεριλαμβάνοντας κόμβους στην υπάρχουσα διαδρομή στο σύνολο επισκέψεων.
ΒΑΣΙΚΕΣ ΔΙΑΦΟΡΕΣ:
- Το BFS βρίσκει τη συντομότερη διαδρομή προς τον προορισμό, ενώ το DFS πηγαίνει στο κάτω μέρος ενός υποδέντρου και μετά ακολουθεί πίσω.
- Η πλήρης μορφή του BFS είναι Breadth-First Search, ενώ η πλήρης μορφή του DFS είναι Depth First Search.
- Το BFS χρησιμοποιεί μια ουρά για να παρακολουθεί την επόμενη τοποθεσία για επίσκεψη. ενώ το DFS χρησιμοποιεί μια στοίβα για να παρακολουθεί την επόμενη τοποθεσία που θα επισκεφτεί.
- Το BFS διασχίζει ανάλογα με το επίπεδο του δέντρου, ενώ το DFS διασχίζει ανάλογα με το βάθος του δέντρου.
- Το BFS υλοποιείται χρησιμοποιώντας τη λίστα FIFO από την άλλη πλευρά Το DFS υλοποιείται χρησιμοποιώντας τη λίστα LIFO.
- Στο BFS, δεν μπορείτε ποτέ να παγιδευτείτε σε πεπερασμένους βρόχους, ενώ στο DFS μπορείτε να παγιδευτείτε σε άπειρους βρόχους.