Αναζήτηση κατά βάθος
Είδος αλγορίθμου αναζήτησης σε γράφους / From Wikipedia, the free encyclopedia
Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο.
Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό Charles Pierre Trémaux [1] ως μια στρατηγική για την επίλυση λαβυρίνθων.[2][3] Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή [4].