Что такое дерево и граф? Обходы BFS и DFS

Что такое граф

Граф — структура данных из вершин и рёбер между ними. Граф может быть ориентированным или неориентированным, взвешенным или невзвешенным, а также может содержать циклы.

Что такое дерево

Дерево — частный случай графа: оно связное и не содержит циклов. В корневом дереве есть root-вершина, а остальные вершины имеют родителя и могут иметь потомков.

BFS — обход в ширину

Breadth-First Search посещает вершины по уровням: сначала стартовую вершину, затем всех её соседей, затем соседей следующего уровня. Для BFS используют очередь.

from collections import deque


def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = {start}
    queue = deque([start])
    result = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

BFS подходит для поиска кратчайшего пути по числу рёбер в невзвешенном графе.

DFS — обход в глубину

Depth-First Search идёт как можно глубже по одной ветке, а затем возвращается назад. Его можно реализовать рекурсией или явным стеком.

def dfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()
    result = []

    def visit(vertex: str) -> None:
        visited.add(vertex)
        result.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visit(neighbor)

    visit(start)
    return result

Зачем нужен visited

В обычном графе могут быть циклы, поэтому без множества visited обход может бесконечно возвращаться к уже посещённым вершинам.

Сложность

И BFS, и DFS посещают каждую достижимую вершину и рассматривают каждое ребро, поэтому их временная сложность равна O(V + E). Дополнительная память для visited и очереди либо стека также может достигать O(V).

Как ответить на собеседовании

Граф состоит из вершин и рёбер, а дерево — это связный граф без циклов. BFS использует очередь и обходит вершины по уровням, поэтому подходит для кратчайшего пути в невзвешенном графе. DFS использует рекурсию или стек и идёт в глубину. Оба алгоритма имеют сложность O(V + E).