Вопрос проверяет знание базовых алгоритмов обхода графов, необходимых для решения задач поиска путей и анализа связей.
Обход графа — это процесс посещения всех вершин графа в определенном порядке. Два фундаментальных алгоритма — поиск в глубину (DFS) и поиск в ширину (BFS). Они различаются стратегией обхода и используемыми структурами данных.
DFS использует стек (явно или через рекурсию) и идет как можно глубже по каждому пути, прежде чем вернуться. Применяется для топологической сортировки, поиска циклов и компонент связности.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visitedBFS использует очередь и обходит граф по уровням: сначала все вершины на расстоянии 1, затем 2 и так далее. Идеален для поиска кратчайшего пути в невзвешенном графе.
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visitedВыбор алгоритма зависит от задачи: BFS для кратчайшего пути в невзвешенном графе, DFS для проверки связности или поиска циклов.
Уровень
Рейтинг:
5
Сложность:
4
Навыки
JavaScript
Python
Ключевые слова
Подпишись на Python Developer в телеграм
