Написать программу, реализующую алгоритм поиска в глубину (DFS) для графа.

Поиск в глубину (DFS) для графа

Алгоритм поиска в глубину (DFS) является основным методом обхода или поиска в деревьях или графах.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start) # Для демонстрации порядка обхода
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

# Пример графа в виде словаря
graph = {
    'A': set(['B', 'C']),
    'B': set(['A', 'D', 'E']),
    'C': set(['A', 'F']),
    'D': set(['B']),
    'E': set(['B', 'F']),
    'F': set(['C', 'E'])
}

# Пример вызова функции
dfs_output = dfs(graph, 'A')

Результат выполнения кода

Порядок обхода: A B D E F C

Эта функция DFS начинает обход с указанной вершины и рекурсивно посещает соседние вершины.

Категория: Практические упражнения Python | Добавил: Admin (03.05.2024)
Просмотров: 20 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *: