🔹 DFS (Depth-First Search) — поиск в глубину в графе

💡Идея:

Исследуем граф «вглубь», пока не достигнем конца пути, затем возвращаемся.

Нужно хранить посещённые вершины (visited).

🔧Применение:

Поиск пути, топологическая сортировка, компоненты связности.

⚙️Рекурсивноя реализвация:

graph = {
    'A': ['B','C'], 'B': ['D','E'], 'C': ['F'],
    'D': [], 'E': ['F'], 'F': []
}

def dfs(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
dfs(graph, 'A')

⚙️Итеративно через стек:

def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            print(v, end=' ')
            visited.add(v)
            stack.extend(reversed(graph[v]))
dfs_iter(graph, 'A')

✅Вывод:

A B D E F C

#algorithm #python