DFS khám phá một đồ thị bằng cách đi sâu nhất có thể dọc theo mỗi nhánh trước khi quay lui (backtracking). Nó dùng một stack (thường là call stack thông qua đệ quy) và thăm trọn một đường đi trước khi khám phá các phương án khác.
Ý tưởng
Từ một nút, đệ quy vào một đỉnh kề chưa được thăm, và tiếp tục đi sâu; khi mắc kẹt, lùi lại và thử một nhánh khác.
Ví dụ
python
():
visited :
visited = ()
visited.add(node)
order = [node]
nbr graph[node]:
nbr visited:
order += dfs(graph, nbr, visited)
order
graph = {: [, ], : [], : [], : []}
dfs(graph, )