Τα BFS και DFS είναι οι μέθοδοι μετακίνησης που χρησιμοποιούνται στην αναζήτηση ενός γραφήματος. Η μετατόπιση γραφήματος είναι η διαδικασία της επίσκεψης σε όλους τους κόμβους του γραφήματος. Ένα γράφημα είναι μια ομάδα Vertices 'V' και Edges 'E' που συνδέεται με τις κορυφές.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | BFS | DFS |
|---|---|---|
| Βασικός | Αλγόριθμος βασισμένος σε κορυφές | Αλγόριθμος βάσει άκρων |
| Δομή δεδομένων που χρησιμοποιείται για την αποθήκευση των κόμβων | Ουρά | Σωρός |
| Κατανάλωση μνήμης | Ανεπαρκής | Αποτελεσματικός |
| Δομή του δομημένου δέντρου | Ευρεία και σύντομη | Στενό και μακρύ |
| Τρέξιμο μόδας | Οι παλιότεροι ανεβασμένοι κόμβοι διερευνώνται αρχικά. | Οι κορυφές κατά μήκος της άκρης εξετάζονται στην αρχή. |
| Βέλτιστη | Βέλτιστο για την εύρεση της μικρότερης απόστασης, χωρίς κόστος. | Δεν είναι βέλτιστη |
| Εφαρμογή | Εξετάζει το διμερές γράφημα, το συνδεδεμένο στοιχείο και τη συντομότερη διαδρομή που υπάρχει σε ένα γράφημα. | Εξετάζει το γράφημα που συνδέεται σε δύο άκρα, το γράφημα που συνδέεται έντονα, το ακυκλικό γράφημα και την τοπολογική σειρά. |
Ορισμός του BFS
Η πρώτη αναζήτηση αρχείων (BFS) είναι η μέθοδος μετακίνησης που χρησιμοποιείται στα γραφήματα. Χρησιμοποιεί μια ουρά για την αποθήκευση των κορυφών επισκέψεων. Σε αυτή τη μέθοδο, η έμφαση δίνεται στις κορυφές του γραφήματος, μια κορυφή επιλέγεται κατά την πρώτη και μετά επιστρέφεται και επισημαίνεται. Οι κορυφές δίπλα στην κορυφή που επισκέπτεται στη συνέχεια επισκέπτονται και αποθηκεύονται στην ουρά διαδοχικά. Παρομοίως, οι αποθηκευμένες κορυφές στη συνέχεια αντιμετωπίζονται μία προς μία και επισκέπτονται οι παρακείμενες κορυφές τους. Ένας κόμβος διερευνάται πλήρως πριν επισκεφτεί κάποιον άλλο κόμβο στο γράφημα, με άλλα λόγια, διασχίζει πρώτους πιο ανεξερεύνητους κόμβους.
Παράδειγμα
Έχουμε ένα γράφημα των οποίων οι κορυφές είναι A, B, C, D, E, F, G. Θεωρώντας το Α ως σημείο εκκίνησης. Τα βήματα που ενέχονται στη διαδικασία είναι:
- Το Vertex A επεκτείνεται και αποθηκεύεται στην ουρά.
- Οι κορυφές B, D και G των διαδόχων του Α, διευρύνθηκαν και αποθηκεύτηκαν στην ουρά εν τω μεταξύ, ο Vertex Α αφαιρέθηκε.
- Τώρα το Β στο εμπρόσθιο άκρο της ουράς αφαιρείται μαζί με την αποθήκευση των διαδοχικών κορυφών Ε και F.
- Το Vertex D βρίσκεται στο εμπρόσθιο άκρο της ουράς αφαιρείται και ο συνδεδεμένος κόμβος F έχει ήδη επισκεφθεί.
- Το Vertex G απομακρύνεται από την ουρά και έχει διάδοχο Ε που έχει ήδη επισκεφθεί.
- Τώρα E και F αφαιρούνται από την ουρά, και η διαδοχική κορυφή C διασχίζεται και αποθηκεύεται στην ουρά.
- Επιτέλους το C αφαιρείται και η ουρά είναι κενή, πράγμα που σημαίνει ότι έχουμε τελειώσει.
- Η παραγόμενη παραγωγή είναι - A, B, D, G, E, F, C.
Το BFS μπορεί να είναι χρήσιμο για να διαπιστώσει εάν το γράφημα έχει συνδεδεμένα στοιχεία ή όχι. Και επίσης μπορεί να χρησιμοποιηθεί για την ανίχνευση ενός διμερούς γραφήματος .
Ένα γράφημα είναι διμερές όταν οι κορυφές γραφημάτων χωρίζονται σε δύο διαφορετικά σύνολα. δεν θα υπάρχουν δύο γειτονικές κορυφές στο ίδιο σετ. Μια άλλη μέθοδος ελέγχου ενός διμερούς γραφήματος είναι να ελέγξετε την εμφάνιση ενός περιττού κύκλου στο γράφημα. Ένα διμερές γράφημα δεν πρέπει να περιέχει περιττό κύκλο.
Το BFS είναι επίσης καλύτερο να βρεθεί η μικρότερη διαδρομή στο γράφημα θα μπορούσε να θεωρηθεί ως δίκτυο.
Ορισμός του DFS
Η μέθοδος μετακίνησης βάθους πρώτης αναζήτησης (DFS) χρησιμοποιεί τη στοίβα για την αποθήκευση των κορυφών επισκέψεων. Το DFS είναι η μέθοδος βασισμένη στις άκρες και λειτουργεί με αναδρομικό τρόπο όπου διεξάγονται οι κορυφές σε μια διαδρομή (άκρη). Η εξερεύνηση ενός κόμβου αναστέλλεται μόλις εντοπιστεί ένας άλλος ανεξερεύνητος κόμβος και οι βαθύτεροι ανεξερεύνητοι κόμβοι διασχίζονται στο ύψιστο σημείο. Το DFS διασχίζει / επισκέπτεται κάθε κορυφή ακριβώς μία φορά και κάθε άκρη ελέγχεται ακριβώς δύο φορές.
Παράδειγμα
Παρόμοια με το BFS, μπορείτε να ακολουθήσετε το ίδιο γράφημα για την εκτέλεση των λειτουργιών DFS και τα βήματα που ακολουθούν είναι:
- Θεωρώντας το Α ως την αρχική κορυφή που διερευνάται και αποθηκεύεται στη στοίβα.
- Η κορυφή Β του διαστήματος A αποθηκεύεται στη στοίβα.
- Η κορυφή B έχει δύο διάδοχους E και F, μεταξύ των οποίων αλφαβητικά το E διερευνάται πρώτα και αποθηκεύεται στη στοίβα.
- Ο διάδοχος της κορυφής Ε, δηλαδή, G αποθηκεύεται στη στοίβα.
- Το Vertex G έχει δύο συνδεδεμένες κορυφές και οι δύο έχουν ήδη επισκεφθεί, οπότε το G βγαίνει από τη στοίβα.
- Παρομοίως, το Es επίσης απομακρύνθηκε.
- Τώρα, η κορυφή B βρίσκεται στην κορυφή της στοίβας, εξερευνήθηκε και αποθηκεύτηκε ένας άλλος κόμβος (κορυφή) F στη στοίβα.
- Το Vertex F έχει δύο διάδοχους C και D, μεταξύ των οποίων το C μετακινείται πρώτα και αποθηκεύεται στη στοίβα.
- Το Vertex C έχει μόνο έναν προκατόχο που έχει ήδη επισκεφθεί, οπότε αφαιρείται από τη στοίβα.
- Τώρα η κορυφή D που είναι συνδεδεμένη με το F επισκέπτεται και αποθηκεύεται στη στοίβα.
- Επειδή η κορυφή D δεν έχει κανέναν ανεπισήμονα κόμβο, ο D απομακρύνεται.
- Παρομοίως, τα F, B και A εμφανίζονται επίσης.
- Η παραγόμενη παραγωγή είναι - A, B, E, G, F, C, D.
Οι εφαρμογές του DFS περιλαμβάνουν την επιθεώρηση ενός γραφήματος που συνδέεται με δύο άκρες, ένα ισχυρά συνδεδεμένο γράφημα, ένα ακυκλικό γράφημα και μια τοπολογική σειρά .
Ένα γράφημα ονομάζεται δύο άκρες που συνδέονται αν και μόνο αν παραμένει συνδεδεμένο ακόμα και αν αφαιρεθεί μία από τις άκρες του. Αυτή η εφαρμογή είναι πολύ χρήσιμη στα δίκτυα υπολογιστών όπου η αποτυχία ενός συνδέσμου στο δίκτυο δεν θα επηρεάσει το υπόλοιπο δίκτυο και θα εξακολουθεί να είναι συνδεδεμένη.
Το ισχυρά συνδεδεμένο γράφημα είναι ένα γράφημα στο οποίο πρέπει να υπάρχει μια διαδρομή μεταξύ του παραγγελθέντος ζεύγους κορυφών. Το DFS χρησιμοποιείται στο κατευθυνόμενο γράφημα για την αναζήτηση της διαδρομής μεταξύ κάθε διατεταγμένου ζεύγους κορυφών. Το DFS μπορεί εύκολα να λύσει προβλήματα συνδεσιμότητας.
Βασικές διαφορές μεταξύ BFS και DFS
- Το BFS είναι ο αλγόριθμος που βασίζεται σε κορυφές, ενώ ο DFS είναι ένας αλγόριθμος βασισμένος στις άκρες.
- Η δομή δεδομένων ουράς χρησιμοποιείται στο BFS. Από την άλλη πλευρά, το DFS χρησιμοποιεί στοίβα ή επανάληψη.
- Ο χώρος μνήμης χρησιμοποιείται αποτελεσματικά στο DFS, ενώ η χρήση χώρου στο BFS δεν είναι αποτελεσματική.
- Το BFS είναι ο βέλτιστος αλγόριθμος, ενώ το DFS δεν είναι βέλτιστο.
- Το DFS κατασκευάζει στενά και μεγάλα δέντρα. Αντιθέτως, το BFS κατασκευάζει πλατύ δέντρο.
συμπέρασμα
BFS και DFS, και οι δύο τεχνικές αναζήτησης γραφημάτων έχουν παρόμοιο χρόνο εκτέλεσης αλλά διαφορετική κατανάλωση χώρου, το DFS παίρνει γραμμικό χώρο επειδή πρέπει να θυμόμαστε μία διαδρομή με ανεξερεύνητους κόμβους, ενώ η BFS κρατά κάθε κόμβο στη μνήμη.
Το DFS αποδίδει βαθύτερες λύσεις και δεν είναι βέλτιστο, αλλά λειτουργεί καλά όταν η λύση είναι πυκνή ενώ η BFS είναι η βέλτιστη που αναζητά πρώτα τον βέλτιστο στόχο.
