Поиск в ширину
- from collections import deque
- graph = {
- 'A' : ['B', 'C', 'E'],
- 'B' : ['A', 'C', 'D'],
- 'C' : ['D'],
- 'D' : ['C'],
- 'E' : ['F', 'D'],
- 'F' : ['C']
- }
- def bfs(g, start):
- queue, enqueued = deque([(None, start)]), set([start])
- while queue:
- parent, n = queue.popleft()
- yield parent, n
- new = set(g[n]) - enqueued
- enqueued |= new
- queue.extend([(n, child) for child in new ])
- def shortest_path(g, start, end):
- paths = {None : []}
- for parent, child in bfs(g, start):
- paths[child] = paths[parent] + [child]
- if child == end:
- return paths[child]
- return None
- >shortest_path(graph, "A", "D")
- ["A", "C", "D"]
Реализация алгоритма поиска короткого пути(алгоритм поиска в ширину) в графе(g) из вершины start в вершину stop. Граф предстовляет собой хэш где ключем являеться имя вершины, а значение массив вершин соеденные с ключем.
