/
Mikhrutka
/
SpecialistPython2_v2
Обзор
Документация
Войти
/
Mikhrutka
/
SpecialistPython2_v2
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
Module7/examples/dfs.py
39 строк
1 KB
boo-learn
fix tasks Module-7
24 июл 2021, 05:23
24 июл 2021, 05:23
3aab6e7
Код
Авторство
О чём код?
# DFS(Depth-First Search) - поиск в глубину # Позволяет построить обход ориентированного или неориентированного графа, # при котором посещаются все вершины, доступные из начальной вершины. # Алгоритм обхода в глубину: # 1. Пойти в какую-нибудь смежную вершину, не посещенную ранее. # 2. Запустить из этой вершины алгоритм обхода в глубину # 3. Вернуться в начальную вершину. # 4. Повторить пункты 1-3 для всех не посещенных ранее смежных вершин. # 3 --5--2 6--7 # / \ / / # 0---1--4 graph = [ # список смежности [1, 3], # 0 [0, 3, 4, 5], # 1 [4, 5], # 2 [0, 1, 5], # 3 [1, 2], # 4 [1, 2, 3], # 5 [7], # 6 [6] # 7 ] visited = [False] * (len(graph)) start = 0 def dfs(v): visited[v] = True for w in graph[v]: if not visited[w]: # посещён ли текущий сосед? dfs(w) dfs(start) print(visited)