DFS — ρητή στοίβα και σειρά επίσκεψης

Python 3 reference program

def dfs(graph, start):
    seen, order, stack = set(), [], [start]
    while stack:
        node = stack.pop()
        if node in seen: continue
        seen.add(node); order.append(node)
        stack.extend(reversed(graph.get(node, ())))
    return order
assert dfs({'a':['b','c'],'b':['d']}, 'a') == ['a','b','d','c']

Μηχανισμός

Η αναζήτηση κατά βάθος εξερευνά ένα μονοπάτι πριν επιστρέψει στους υπόλοιπους γείτονες. Το πρόγραμμα χρησιμοποιεί LIFO stack αντί για αναδρομή, οπότε αποφεύγει τα recursion-depth όρια μακριών αλυσίδων. Η ρητή στοίβα εξακολουθεί να χρειάζεται μνήμη έως O(V).

Γιατί γίνεται reversed

Οι γείτονες μπαίνουν στη στοίβα με αντίστροφη σειρά, ώστε κατά το pop να εξεταστεί πρώτος ο αριστερότερος. Για a→b,c και b→d η σειρά είναι a,b,d,c. Χωρίς reversed θα προηγούνταν το c. Η σειρά εξαρτάται από τη λίστα γειτόνων και δεν αποτελεί σταθερή ιδιότητα κάθε DFS.

Εργαστήριο

1. Πρόσθεσε ακμή c→a. Το seen αποτρέπει πολλαπλές επισκέψεις λόγω κύκλου.
2. Πρόσθεσε δύο ίδιες ακμές a→b. Μπορούν να μπουν προσωρινά διπλά στοιχεία στη στοίβα αλλά η έξοδος πρέπει να έχει το b μία φορά.
3. Δοκίμασε αλυσίδα 10000 κόμβων και σύγκρινε iterative με recursive μέθοδο, λαμβάνοντας υπόψη τα όρια αναδρομής.
4. Πρόσθεσε αποσυνδεδεμένο z. Η εκκίνηση από a δεν το επισκέπτεται· για ολόκληρο γράφο ξεκίνα νέα DFS από κάθε αθέατο vertex.
5. Άλλαξε τη σειρά των γειτόνων και έλεγξε τη νέα σειρά. Αν η σειρά δεν είναι απαίτηση, σύγκρινε σύνολα επισκέψεων.

Όρια

Η DFS δεν εγγυάται συντομότερο μονοπάτι. Για εντοπισμό κύκλων σε directed graph χρειάζεται και πληροφορία ενεργού μονοπατιού ή χρώματα, όχι μόνο seen. Σε adjacency list χρόνος O(V+E), μνήμη έως O(V).

07 dfs — έλεγχος ορίων

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

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

<!-- [curated-algorithm-detail:07_dfs.md] -->

Ρητά πλαίσια DFS που διατηρούν μεταδιάταξη

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

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

children = {"a":["b","c"], "b":["d"], "c":[], "d":[]}
stack = [("a", False)]
postorder = []
while stack:
    node, exiting = stack.pop()
    if exiting:
        postorder.append(node)
    else:
        stack.append((node, True))
        stack.extend((child, False) for child in reversed(children[node]))
assert postorder == ["d","b","c","a"]
print(postorder)

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

Τεχνική αναφορά