Обход в глубину (DFS)

https://t.me/solidityset

Пример 1

def dfs(graph, start_node, visited=None):
    """Обход графа в глубину (рекурсивный)."""
    
    # При первом вызове создаём пустое множество посещённых узлов
    # Почему не visited=set() в аргументах? Это ловушка Python:
    # изменяемые объекты по умолчанию создаются ОДИН РАЗ для всех вызовов!
    if visited is None:
        visited = set()
    
    visited.add(start_node)      # Помечаем текущий узел как посещённый
    result = [start_node]        # Добавляем его в результат
    
    for neighbor in graph.get(start_node, []):   # Для каждого соседа
        if neighbor not in visited:              # Если ещё не были там
            result.extend(dfs(graph, neighbor, visited))  # Уходим глубже!
            
    return result


# Наш граф
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

print(dfs(graph, "A"))
# Вывод: ['A', 'B', 'D', 'E', 'F', 'C']

Пример 2

dfs(A)
  ├─ visited = {A}, result = [A]
  ├─ сосед B → не посещён
  │    dfs(B)
  │      ├─ visited = {A,B}, result = [B]
  │      ├─ сосед A → уже посещён, пропуск
  │      ├─ сосед D → не посещён
  │      │    dfs(D)
  │      │      ├─ visited = {A,B,D}, result = [D]
  │      │      ├─ сосед B → уже посещён, пропуск
  │      │      └─ return [D]          ← ТУПИК, возврат
  │      ├─ сосед E → не посещён
  │      │    dfs(E)
  │      │      ├─ visited = {A,B,D,E}, result = [E]
  │      │      ├─ сосед B → уже посещён, пропуск
  │      │      ├─ сосед F → не посещён
  │      │      │    dfs(F)
  │      │      │      ├─ visited = {A,B,D,E,F}, result = [F]
  │      │      │      ├─ сосед C → не посещён
  │      │      │      │    dfs(C)
  │      │      │      │      ├─ visited = {A,B,D,E,F,C}, result = [C]
  │      │      │      │      ├─ сосед A → посещён, пропуск
  │      │      │      │      ├─ сосед F → посещён, пропуск
  │      │      │      │      └─ return [C]
  │      │      │      ├─ сосед E → посещён, пропуск
  │      │      │      └─ return [F, C]
  │      │      └─ return [E, F, C]
  │      └─ return [B, D, E, F, C]
  └─ return [A, B, D, E, F, C]

Пример 3

def dfs_iterative(graph, start_node):
    """Обход графа в глубину (итеративный, с явным стеком)."""
    
    visited = set()       # Множество посещённых узлов
    stack = [start_node]  # Стек: начинаем с начального узла
    result = []
    
    while stack:                        # Пока стек не пуст
        node = stack.pop()              # Берём верхний элемент стека
        
        if node in visited:             # Если уже посещали — пропускаем
            continue
            
        visited.add(node)               # Помечаем как посещённый
        result.append(node)             # Добавляем в результат
        
        # Добавляем соседей в стек (в обратном порядке, чтобы сохранить
        # тот же порядок обхода, что и в рекурсивной версии)
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return result


print(dfs_iterative(graph, "A"))
# Вывод: ['A', 'B', 'D', 'E', 'F', 'C']

Пример 4

def has_cycle(graph):
    """Определяет наличие цикла в ориентированном графе."""
    
    visited = set()      # Все посещённые узлы
    rec_stack = set()    # Узлы в текущем пути рекурсии
    
    def dfs_cycle(node):
        visited.add(node)
        rec_stack.add(node)    # Вошли в узел — добавляем в путь
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs_cycle(neighbor):    # Рекурсивно проверяем
                    return True
            elif neighbor in rec_stack:    # Сосед уже в нашем пути — ЦИКЛ!
                return True
        
        rec_stack.remove(node)    # Покидаем узел — убираем из пути
        return False
    
    # Запускаем DFS из каждого непосещённого узла
    # (граф может быть несвязным)
    for node in graph:
        if node not in visited:
            if dfs_cycle(node):
                return True
    
    return False


# Тест 1: граф без цикла
graph_no_cycle = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": [],
    "D": []
}
print(has_cycle(graph_no_cycle))   # False

# Тест 2: граф с циклом (B → D → B)
graph_with_cycle = {
    "A": ["B"],
    "B": ["D"],
    "D": ["B"]   # ← вот он, цикл!
}
print(has_cycle(graph_with_cycle))   # True

Пример 5

Обход graph_with_cycle:

dfs(A):
  rec_stack = {A}
  → сосед B, не посещён
    dfs(B):
      rec_stack = {A, B}
      → сосед D, не посещён
        dfs(D):
          rec_stack = {A, B, D}
          → сосед B, уже посещён И находится в rec_stack!
          ← ЦИКЛ НАЙДЕН! return True

Пример 6

# DFS для поиска любого пути в лабиринте
def find_exit_dfs(maze, start, exit_point):
    """
    maze: словарь {узел: [соседи]}
    Возвращает путь от start до exit_point, если он существует.
    """
    visited = set()
    path = []
    
    def dfs(node):
        if node in visited:
            return False
        
        visited.add(node)
        path.append(node)
        
        if node == exit_point:       # Нашли выход!
            return True
        
        for neighbor in maze.get(node, []):
            if dfs(neighbor):        # Если этот путь ведёт к выходу
                return True
        
        path.pop()                   # Тупик — убираем из пути (backtracking)
        return False
    
    if dfs(start):
        return path
    return None   # Выхода нет


# Простой лабиринт в виде графа
maze = {
    "S": ["A", "B"],
    "A": ["S", "C"],
    "B": ["S", "D"],
    "C": ["A", "E"],
    "D": ["B", "E"],
    "E": ["C", "D", "EXIT"],
    "EXIT": ["E"]
}

print(find_exit_dfs(maze, "S", "EXIT"))
# Один из возможных путей: ['S', 'A', 'C', 'E', 'EXIT']