Qu'est-ce qu'un graphe ? Algorithmes de parcours de graphe ?

Граф — это структура данных, состоящая из множества узлов (вершин) и связей между ними (рёбер). Графы используются для моделирования сетей, маршрутов, зависимостей и других отношений.

Основные алгоритмы обхода графа:

• Обход в глубину (DFS, Depth-First Search): начинается с выбранной вершины, затем рекурсивно посещает соседние вершины, углубляясь как можно дальше по каждой ветке перед возвратом.

• Обход в ширину (BFS, Breadth-First Search): начинается с выбранной вершины и посещает все соседние вершины на текущем уровне, затем переходит к следующему уровню.

Пример обхода в глубину на Python:

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

visited = set()

def dfs(node):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(neighbour)

dfs('A')

Этот код выведет вершины в порядке обхода в глубину, начиная с 'A'.