DFS εξερευνά ένα γράφημα πηγαίνοντας όσο πιο βαθιά γίνεται σε κάθε κλάδο πριν οπισθοχωρήσει. Χρησιμοποιεί μια stack (συχνά την stack κλήσης μέσω αναδρομής) και επισκέπτεται μια πλήρη διαδρομή πριν εξερευνήσει εναλλακτικές λύσεις.
Η ιδέα
Από έναν κόμβο, κάνε αναδρομή σε έναν ανεπίσκεπτο γείτονα και συνέχισε να πηγαίνεις βαθιά· όταν κολλήσεις, οπισθοχώρησε και δοκίμασε έναν άλλο κλάδο.
Παράδειγμα
():
visited :
visited = ()
visited.add(node)
order = [node]
nbr graph[node]:
nbr visited:
order += dfs(graph, nbr, visited)
order
graph = {: [, ], : [], : [], : []}
dfs(graph, )
