BFS εναντίον DFS – Διαφορά μεταξύ τους

Τι είναι το BFS;

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

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

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

Τι είναι το DFS;

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

Διαφορά μεταξύ BFS και DFS Binary Tree

Εδώ είναι οι σημαντικές διαφορές μεταξύ BFS και DFS.

BFS	DFS
BFS βρίσκει το συντομότερο μονοπάτι προς τον προορισμό.	Το DFS πηγαίνει στο κάτω μέρος ενός υποδένδρου και μετά πίσωtracks.
Η πλήρης μορφή του BFS είναι Breadth-First Search.	Η πλήρης μορφή του DFS είναι το Depth First Search.
Χρησιμοποιεί μια ουρά για να διατηρεί track της επόμενης τοποθεσίας που θα επισκεφθείτε.	Χρησιμοποιεί μια στοίβα για να διατηρεί track της επόμενης τοποθεσίας που θα επισκεφθείτε.
Το BFS διασχίζει ανάλογα με το επίπεδο του δέντρου.	Το DFS διασχίζει ανάλογα με το βάθος του δέντρου.
Υλοποιείται χρησιμοποιώντας τη λίστα FIFO.	Υλοποιείται χρησιμοποιώντας τη λίστα LIFO.
Απαιτεί περισσότερη μνήμη σε σύγκριση με το DFS.	Απαιτεί λιγότερη μνήμη σε σύγκριση με το BFS.
Αυτός ο αλγόριθμος δίνει τη λύση της πιο ρηχής διαδρομής.	Αυτός ο αλγόριθμος δεν εγγυάται τη λύση της πιο ρηχής διαδρομής.
Δεν υπάρχει ανάγκη για επιστροφήtracβασιλιάς στο BFS.	Υπάρχει ανάγκη για επιστροφήtracβασιλιάς στο DFS.
Δεν μπορείτε ποτέ να παγιδευτείτε σε πεπερασμένους βρόχους.	Μπορείτε να παγιδευτείτε σε άπειρους βρόχους.
Εάν δεν βρείτε κανέναν στόχο, ίσως χρειαστεί να επεκτείνετε πολλούς κόμβους πριν βρεθεί η λύση.	Αν δεν βρείτε κανένα στόχο, ο κόμβος φύλλου επιστρέφειtracμπορεί να συμβεί βασιλιάς.

Παράδειγμα BFS

Στο παρακάτω παράδειγμα του BFS, χρησιμοποιήσαμε γράφημα με 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

Εδώ, είναι οι Εφαρμογές του BFS:

Μη σταθμισμένα γραφήματα

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

Δίκτυα P2P

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

Ανιχνευτές Ιστού

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

Δικτυακή Εκπομπή

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

Εφαρμογές DFS

Ακολουθούν σημαντικές εφαρμογές του DFS:

Σταθμισμένο γράφημα

Σε ένα σταθμισμένο γράφημα, η διέλευση γραφήματος DFS δημιουργεί το δέντρο της συντομότερης διαδρομής και το ελάχιστο εκτεινόμενο δέντρο.

Ανίχνευση ενός κύκλου σε ένα γράφημα

Ένα γράφημα έχει έναν κύκλο αν εντοπίσουμε ένα πίσω άκρο κατά τη διάρκεια του DFS. Επομένως, θα πρέπει να εκτελέσουμε το DFS για το γράφημα και να επαληθεύσουμε για τις πίσω άκρες.

Εύρεση Διαδρομών

Μπορούμε να ειδικευτούμε στον αλγόριθμο DFS για να αναζητήσουμε μια διαδρομή μεταξύ δύο κορυφών.

Τοπολογική ταξινόμηση

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

Αναζήτηση ισχυρά συνδεδεμένων στοιχείων ενός γραφήματος

Χρησιμοποιείται στο γράφημα DFS όταν υπάρχει μια διαδρομή από κάθε κορυφή του γραφήματος προς άλλες εναπομείνασες κορυφές.

Επίλυση γρίφων με μία μόνο λύση

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