Викиучебник

Реализации алгоритмов/Поиск в ширину: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Скопировано из w:Поиск в ширину
Строка 8:
== [[Python]] ==
<source lang="python">
adj = [ # список смежности
def BFS(s,Adj):▼
level = {[1,3], s:# 0 }
[0,3,4,5], # 1
parent = { s: None }
i = 1[4,5], # 2
frontier = [s0,1,5], # 3
[1,2], # 4
while frontier:
next = [1,2,3] # 5
]
for u in frontier:
 
for v in Adj[u]:
level = [-1] * len(adj) # список уровней вершин
if v not in level:
 
level[v] = i
▲def BFSbfs(s,Adj):
parent[v] = u
level[s] = 0 # уровень начальной вершины
next.append(v)
stack = [s] # добавляем начальную вершину в очередь
frontier = next
while stack: # пока там что-то есть
i += 1
v = stack.pop(0) # извлекаем вершину
for w in adj[v]: # запускаем обход из вершины v
if level[w] is -1: # проверка на посещенность
stack.append(w) # добавление вершины в очередь
level[w] = level[v] + 1 # подсчитываем уровень вершины
 
bfs(0) # обход из вершины 0
print(level[2]) # уровень вершины 2
</source>
 
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Поиск_в_ширину