Σε DFS , οι κόμβοι που εξερευνώνται αποθηκεύονται σε μια δομή δεδομένων στοίβας. Οι ακμές που μας κατευθύνουν σε ανεξερεύνητους κόμβους ονομάζονται « άκρες ανακάλυψης «ενώ οι άκρες που πρόκειται να οδηγήσουν κόμβους που έχουν ήδη επισκεφθεί ονομάζονται» μπλοκ άκρες '. DFS είναι χρήσιμο σε σενάρια όταν ένας προγραμματιστής θέλει να βρει συνδεδεμένα στοιχεία ή κύκλους σε ένα γράφημα.
Ακολουθήστε τις οδηγίες αυτού του άρθρου για εφαρμογή DFS σε C++.
Υλοποίηση DFS σε C++
Στην επόμενη ενότητα, θα δούμε πώς DFS υλοποιείται σε C++. Μπορεί κανείς να ακολουθήσει τα βήματα που δίνονται για να εφαρμόσει DFS .
- Εισαγάγετε τον ριζικό κόμβο ενός δέντρου ή γραφήματος στη στοίβα.
- Προσθέστε το κορυφαίο στοιχείο της στοίβας στη λίστα επισκέψεων.
- Ανακαλύψτε όλους τους παρακείμενους κόμβους στον κόμβο που επισκεφτήκατε και προσθέστε αυτούς τους κόμβους που δεν έχουν επισκεφτεί ακόμη τη στοίβα.
- Επαναλάβετε τα βήματα 2 και 3 μέχρι να αδειάσει η στοίβα.
Ψευκώδικας DFS
ο DFS Ο ψευδοκώδικας φαίνεται παρακάτω. Στο θερμότητα() λειτουργία, εκτελούμε μας DFS λειτουργία σε κάθε κόμβο. Επειδή το γράφημα μπορεί να έχει δύο αποσυνδεδεμένα μέρη, μπορούμε να εκτελέσουμε το DFS αλγόριθμος σε κάθε κόμβο για να διασφαλίσουμε ότι έχουμε καλύψει κάθε κορυφή.
DFS ( ζ α )
ένα. επισκέφθηκε = αληθής
Για κάθε β ∈ g. Επίθ [ ένα ]
αν σι. επισκέφθηκε == ψευδής
DFS ( γιγαμπάιτ )
θερμότητα ( )
{
Για κάθε ∈ g
ένα. επισκέφθηκε = ψευδής
Για κάθε ∈ g
DFS ( ζ, α )
}
Εδώ τα g, a και b αντιπροσωπεύουν το γράφημα, τον κόμβο που επισκέφτηκε για πρώτη φορά και τον κόμβο στη στοίβα αντίστοιχα.
Εφαρμογή DFS σε C++
Ένα πρόγραμμα C++ για DFS η υλοποίηση δίνεται παρακάτω:
#include
#include
#include
χρησιμοποιώντας χώρο ονομάτων std ;
πρότυπο < όνομα τύπου t >
τάξη DepthFirstSearch
{
ιδιωτικός :
χάρτης < t,λίστα < t > > adjList ;
δημόσιο :
DepthFirstSearch ( ) { }
κενός Add_edge ( t a, t b, bool εσείς = αληθής )
{
adjList [ ένα ] . push_back ( σι ) ;
αν ( εσείς )
{
adjList [ σι ] . push_back ( ένα ) ;
}
}
κενός Prnt ( )
{
Για ( αυτο Εγώ : adjList ) {
cout << Εγώ. πρώτα << '->' ;
Για ( t είσοδος : Εγώ. δεύτερος ) {
cout << είσοδος << ',' ;
}
cout << endl ;
}
}
κενός dfs_helper ( t κόμβος, χάρτης < t, bool > & επισκέφθηκε ) {
επισκέφθηκε [ κόμβος ] = αληθής ;
cout << κόμβος << '' << endl ;
Για ( t γείτονας : adjList [ κόμβος ] ) {
αν ( ! επισκέφθηκε [ γείτονας ] ) {
dfs_helper ( γείτονας, επισκέφθηκε ) ;
}
}
}
κενός DFS ( t src )
{
χάρτης < t, bool > επισκέφθηκε ;
dfs_helper ( src, επισκέφτηκε ) ;
}
} ;
ενθ κύριος ( ) {
DepthFirstSearch < ενθ > σολ ;
σολ. Add_edge ( 0 , 5 ) ;
σολ. Add_edge ( 0 , 7 ) ;
σολ. Add_edge ( 4 , 7 ) ;
σολ. Add_edge ( 7 , 8 ) ;
σολ. Add_edge ( 2 , 1 ) ;
σολ. Add_edge ( 0 , 6 ) ;
σολ. Add_edge ( 2 , 4 ) ;
σολ. Add_edge ( 3 , 2 ) ;
σολ. Add_edge ( 3 , 6 ) ;
σολ. Add_edge ( 7 , 5 ) ;
σολ. Add_edge ( 5 , 8 ) ;
σολ. Prnt ( ) ;
σολ. DFS ( 6 ) ;
cout << endl ;
}
Σε αυτόν τον κώδικα, έχουμε εφαρμόσει DFS αλγόριθμος που ακολουθεί τον ψευδοκώδικα που δίνεται παραπάνω. Έχουμε 12 ζεύγη κόμβων. Ορίσαμε μια τάξη ' σολ ” το οποίο αντιπροσωπεύει ένα γράφημα με κορυφές a και b που αντιπροσωπεύουν κόμβους που έχουν επισκεφθεί και μη επισκέψιμο.
Παραγωγή
συμπέρασμα
DFS είναι ένας δημοφιλής αλγόριθμος αναζήτησης χρήσιμος για πολλά σενάρια, όπως η εύρεση των κύκλων σε ένα γράφημα και η λήψη πληροφοριών σχετικά με τα συνδεδεμένα στοιχεία ή όλες τις κορυφές σε ένα γράφημα. Περιγράψαμε επίσης τη λειτουργία του DFS μέθοδος με παράδειγμα. DFS χρησιμοποιεί στοίβες για την εκτέλεση της τεχνικής και μπορεί επίσης να χρησιμοποιηθεί σε δέντρα.