Αυτό το άρθρο παρουσιάζει τη διαδικασία υλοποίησης του DFS για ένα παρεχόμενο δέντρο ή γράφημα.
Πώς να εφαρμόσετε την Πρώτη Αναζήτηση Βάθους ή το DFS για ένα γράφημα στην Java;
Το DFS χρησιμοποιείται κυρίως για την αναζήτηση ενός γραφήματος με επίσκεψη σε κάθε κλάδο/κορυφή ακριβώς μία φορά. Μπορεί να ανιχνεύσει ή να αναγνωρίσει κύκλους σε ένα γράφημα που βοηθά στην αποφυγή αδιεξόδων. Μπορεί να χρησιμοποιηθεί για την επίλυση παζλ ή προβλημάτων λαβύρινθου. Το DFS μπορεί να εφαρμοστεί/χρησιμοποιηθεί σε αλγόριθμους γραφημάτων, ανίχνευση ιστού και σχεδιασμό μεταγλωττιστή.
Για εξηγήσεις, επισκεφτείτε τον παρακάτω κώδικα της Πρώτης Αναζήτησης Βάθους ή του DFS:
τάξη Γραφική παράσταση {
ιδιωτικός LinkedList addNode [ ] ;
ιδιωτικός boolean Διασχίστηκε [ ] ;
Γραφική παράσταση ( ενθ κορυφές ) {
addNode = νέος LinkedList [ κορυφές ] ;
Διασχίστηκε = νέος boolean [ κορυφές ] ;
Για ( ενθ Εγώ = 0 ; Εγώ < κορυφές ; Εγώ ++ )
addNode [ Εγώ ] = νέος LinkedList ( ) ;
}
κενός addEdge ( ενθ src, ενθ αρχή ) {
addNode [ src ] . Προσθήκη ( αρχή ) ;
}
Περιγραφή του παραπάνω κώδικα:
- Πρώτα, η τάξη με το όνομα ' Γραφική παράσταση ' δημιουργειται. Μέσα σε αυτό, δηλώνει ένα ' LinkedList 'με όνομα' addNode[] ' και έναν πίνακα τύπου boolean με το όνομα ' Διασχίστηκε[] '.
- Στη συνέχεια, περάστε τις κορυφές για τον κατασκευαστή του ' Γραφική παράσταση ” κατηγορία ως παράμετρος.
- Μετά από αυτό, το « Για Ο βρόχος ” δημιουργείται για να μετακινείται σε κάθε κόμβο του επιλεγμένου κλάδου.
- Στο τέλος, ο τύπος κενού ' addEdge() ' χρησιμοποιείται για την προσθήκη ακμών μεταξύ κορυφών. Αυτή η συνάρτηση παίρνει δύο παραμέτρους: την πηγή της κορυφής ' src ' και η κορυφή προορισμού ' αρχή '.
Μετά τη δημιουργία ενός γραφήματος, ας προσθέσουμε τώρα κώδικα αναζήτησης σε βάθος ή DFS για το γράφημα που δημιουργήθηκε παραπάνω:
κενός DFS ( ενθ κορυφή ) {
Διασχίστηκε [ κορυφή ] = αληθής ;
Σύστημα . έξω . Τυπώνω ( κορυφή + '' ) ;
Iterator Αυτό = addNode [ κορυφή ] . listIterator ( ) ;
ενώ ( Αυτό. έχειΕπόμενο ( ) ) {
ενθ επίθ = Αυτό. Επόμενο ( ) ;
αν ( ! Διασχίστηκε [ επίθ ] )
DFS ( επίθ ) ;
}
}
Στο παραπάνω μπλοκ κώδικα:
- Πρώτον, το « DFS() ' Δημιουργείται η συνάρτηση που παίρνει ' κορυφή ” ως παράμετρος. Αυτή η κορυφή επισημαίνεται ως επίσκεψη.
- Στη συνέχεια, εκτυπώστε την κορυφή που επισκεφτήκατε χρησιμοποιώντας το ' out.print() 'μέθοδος.
- Στη συνέχεια, δημιουργήστε ένα παράδειγμα του ' Iterator ” που επαναλαμβάνεται πάνω από τις γειτονικές κορυφές της τρέχουσας κορυφής.
- Εάν η κορυφή δεν επισκέπτεται, τότε μεταβιβάζει αυτήν την κορυφή στο ' DFS() ' λειτουργία.
Τώρα, ας δημιουργήσουμε ένα ' κύριος() ” τμήμα συνάρτησης για να δημιουργήσετε το γράφημα και στη συνέχεια να εφαρμόσετε το DFS σε αυτό:
δημόσιο στατικός κενός κύριος ( Σειρά args [ ] ) {
Γράφημα ια = νέος Γραφική παράσταση ( 4 ) ;
κ. addEdge ( 0 , 1 ) ;
κ. addEdge ( 1 , 2 ) ;
κ. addEdge ( 2 , 3 ) ;
κ. addEdge ( 3 , 3 ) ;
Σύστημα . έξω . println ( 'Following is Depth First Traversal' ) ;
κ. DFS ( 1 ) ;
}
}
Επεξήγηση του παραπάνω κώδικα:
- Πρώτα, δημιουργήστε ένα αντικείμενο ' κ ' για το ' Γραφική παράσταση() 'μέθοδος.
- Στη συνέχεια, το « addEdge() Η μέθοδος ' χρησιμοποιείται για την προσθήκη ακμών μεταξύ πολλαπλών κορυφών. Αυτό δημιουργεί τη δομή του γραφήματος μας.
- Στο τέλος, περάστε οποιαδήποτε τιμή κορυφής ως όρισμα στο ήδη δημιουργημένο ' DFS() ' λειτουργία. Για να βρείτε αυτή τη διαδρομή κορυφής από τη ρίζα, χρησιμοποιήστε έναν αλγόριθμο αναζήτησης κατά βάθος. Για παράδειγμα, μια τιμή ' 1 ' μεταβιβάζεται στο ' DFS() ' λειτουργία.
Μετά το τέλος της φάσης σύνταξης:
Η έξοδος δείχνει ότι η αναζήτηση πρώτα σε βάθος έχει υλοποιηθεί με επιτυχία.
συμπέρασμα
Το Depth First Search είναι ένας αλγόριθμος διέλευσης γραφήματος που αποτελεί τη βάση για πολλούς αλγόριθμους γραφημάτων, όπως η εύρεση της συντομότερης διαδρομής, τα δέντρα και η ανάλυση συνδεσιμότητας. Ξεκινά από τον ριζικό κόμβο και στη συνέχεια μετακινείται όσο το δυνατόν πιο βαθιά μέχρι τον κόμβο αποχώρησης ή τον τελευταίο κόμβο αυτού του κλάδου πριν από την αναδρομή. Αυτό το άρθρο έχει δείξει τη διαδικασία για την υλοποίηση της αναζήτησης πρώτα σε βάθος ή DFS για ένα γράφημα σε Java.