depth.md

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

| Главная | Графы |

Поиск в глубину (англ. depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

Реализация

• Без использования рекурсии, используя список смежности

Время	Память
O(V + E)	O(V)

def dfs(graph, start):
    visited = dict().fromkeys(graph, False) # False - белая вершина, True - черная вершина
    stack = [start]
    while stack:
        v = stack.pop()
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                stack.append(u)
    return visited

    
g = {
    0: [],
    1: [3, 6],
    2: [0, 1, 4],
    3: [5],
    4: [2],
    5: [7],
    6: [2],
    7: []
}


print(dfs(g, 1)) #  {0: True, 1: True, 2: True, 3: True, 4: True, 5: True, 6: True, 7: True}