DFS — Επεξήγηση του αλγορίθμου αναζήτησης σε βάθος

Η αναζήτηση σε βάθος, ή DFS, είναι ένας αλγόριθμος για την εξερεύνηση ενός δέντρου ή γράφου ακολουθώντας ένα μονοπάτι όσο πιο μακριά γίνεται πριν κάνει backtracking. Με απλά λόγια: το DFS συνεχίζει να πηγαίνει πιο βαθιά μέχρι να κολλήσει και μετά επιστρέφει στο τελευταίο σημείο όπου υπάρχει διαθέσιμος άλλος κλάδος.

Αν θυμάσαι μία μόνο ιδέα, να θυμάσαι αυτή: DFS σημαίνει «πήγαινε βαθιά και μετά γύρνα πίσω».

Τι κάνει η αναζήτηση σε βάθος

Το DFS μπορεί να χρησιμοποιηθεί σε δέντρα και σε γενικούς γράφους. Ξεκινώντας από έναν κόμβο, μετακινείται επανειλημμένα σε έναν μη επισκέψιμο γείτονα. Όταν φτάσει σε έναν κόμβο που δεν έχει άλλον μη επισκέψιμο γείτονα, κάνει backtracking στον προηγούμενο κόμβο και συνεχίζει από εκεί.

Αυτό το backtracking είναι το χαρακτηριστικό του συμπεριφοράς. Στις αναδρομικές υλοποιήσεις, η στοίβα κλήσεων το διαχειρίζεται αυτόματα. Στις επαναληπτικές υλοποιήσεις, μια ρητή στοίβα παίζει τον ίδιο ρόλο.

Γιατί η σειρά του DFS μπορεί να αλλάζει

Το DFS δεν παράγει μία καθολική σειρά επίσκεψης. Η ακριβής σειρά εξαρτάται από τη σειρά με την οποία εξετάζονται οι γείτονες.

Για παράδειγμα, αν ένας κόμβος έχει γείτονες τους $B$ και $C$, το να επισκεφθείς πρώτα το $B$ μπορεί να δώσει διαφορετική σειρά DFS από το να επισκεφθείς πρώτα το $C$. Η αναζήτηση παραμένει DFS και στις δύο περιπτώσεις, επειδή ο κανόνας είναι ο ίδιος: συνέχισε να πηγαίνεις πιο βαθιά πριν εξερευνήσεις έναν αδελφό κλάδο.

Παράδειγμα DFS σε έναν μικρό γράφο

Ας υποθέσουμε ότι ο γράφος έχει τις εξής συνδέσεις:

• Το $A$ συνδέεται με τα $B$ και $C$
• Το $B$ συνδέεται με τα $D$ και $E$
• Το $C$ συνδέεται με το $F$

Υποθέτουμε ότι εξετάζουμε πάντα τους γείτονες από αριστερά προς τα δεξιά και ξεκινάμε από το $A$.

Το DFS προχωρά ως εξής:

1. Επισκέψου το $A$
2. Πήγαινε στο $B$
3. Πήγαινε στο $D$
4. Το $D$ δεν έχει μη επισκέψιμο γείτονα, οπότε κάνε backtrack στο $B$
5. Από το $B$, πήγαινε στο $E$
6. Το $E$ ολοκληρώθηκε, οπότε κάνε backtrack στο $B$ και μετά στο $A$
7. Από το $A$, πήγαινε στο $C$
8. Από το $C$, πήγαινε στο $F$

Άρα μία έγκυρη σειρά επίσκεψης DFS είναι:

$$A, B, D, E, C, F$$

Η βασική ιδέα είναι ότι το DFS ολοκληρώνει την πλευρά $A \to B$ πριν ξεκινήσει την πλευρά $A \to C$. Αν άλλαζες τη σειρά των γειτόνων, θα μπορούσε να αλλάξει και η σειρά επίσκεψης.

Γιατί το backtracking χρησιμοποιεί στοίβα

Το DFS χρειάζεται πάντα έναν τρόπο να θυμάται πού πρέπει να επιστρέψει αφού φτάσει σε αδιέξοδο. Γι’ αυτό οι στοίβες εμφανίζονται φυσικά στο DFS.

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

Χρονική και χωρική πολυπλοκότητα του DFS

Αν ο γράφος αποθηκεύεται ως λίστα γειτνίασης και κάθε κορυφή σημειώνεται την πρώτη φορά που επισκέπτεται, το DFS εκτελείται σε

$$O(V + E)$$

χρόνο για το προσβάσιμο τμήμα του γράφου, όπου $V$ είναι ο αριθμός των κορυφών και $E$ ο αριθμός των ακμών.

Ο επιπλέον χώρος είναι συνήθως

$$O(V)$$

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

Συνηθισμένα λάθη στο DFS

Να ξεχνάς να σημειώνεις τους επισκέψιμους κόμβους

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

Να υποθέτεις ότι το DFS βρίσκει το συντομότερο μονοπάτι

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

Να θεωρείς ότι η σειρά του DFS είναι μοναδική

Η σειρά εξαρτάται από τη σειρά των γειτόνων. Αν αυτή η σειρά αλλάξει, μπορεί να αλλάξει και η σειρά διάσχισης.

Πότε χρησιμοποιείται η αναζήτηση σε βάθος

Το DFS είναι χρήσιμο όταν θέλεις να εξερευνήσεις τη δομή και όχι απλώς την κοντινότερη απόσταση πρώτα. Συνηθισμένες χρήσεις περιλαμβάνουν:

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

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

DFS έναντι BFS: η πρακτική διαφορά

Το DFS κατεβαίνει πρώτα σε έναν κλάδο. Το BFS εξερευνά όλους τους κόμβους σε μία απόσταση πριν προχωρήσει στην επόμενη απόσταση.

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

Δοκίμασε μια παρόμοια διάσχιση

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