Поиск в глубину DFS в Python
DFS использует рекурсию или явный стек.
Что такое Поиск в глубину DFS в Python?
DFS использует рекурсию или явный стек.
Исследуйте путь до конца перед возвратом.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Визуализация: Поиск в глубину DFS в Python
O(V+E)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))Ожидаемый результат
['A', 'B', 'D', 'C', 'E']Как это работает
Каждая вершина и ребро обрабатываются не более раза: O(V+E).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.