Поиск в глубину

Поиск в глубину (DFS: Depth-First Search) - это алгоритм обхода графа, который хочет как можно “глубже” уйти в граф.

(синие стрелки – вглубь графа, красные – обратно)

Алгоритм описывается рекурсивно. Если вершина не обработана, она обрабатывается и обрабатываются ее соседи. Если у вершины нет соседей, алгоритм переходит на уровень выше.

Сперва задаем граф в виде списка смежности.

    graph = [
        [1, 2],
        [0, 2, 3],
        [0, 1, 4],
        [1, 4],
        [2, 3, 5],
        [4, 6],
        [5]
    ]
  

Затем заводим массив, где $i$-му индексу будет присвоено значение True, если $i$-ая вершина была посещена, или False иначе.

Приступим к написанию функции.

    used = [False for _ in range(len(graph))] # Изначально никакие вершины не посещены.

    def dfs(vert):
        print(vert)
        used[vert] = True # Отмечаем, что вершина посещена.
        for neib in graph[vert]:
            if not used[neib]:
                dfs(neib)

Каждый раз, когда мы посещаем вершину, мы ее сперва обрабатываем, в самом массиве отмечаем, что вершина посещена. Потом проходимся по соседям. Если окажется, что по индексу соседа в массиве записано значение False, то алгоритм проделывается на нем. Если у вершины нет соседей или они все обработаны, то функция завершается.