Встречается на собеседованиях • сегодня
Что такое bi-connection для алгоритмов
Bi-connection (или двунаправленный поиск) — это техника оптимизации алгоритмов поиска, при которой поиск выполняется одновременно из начальной и конечной точек, пока они не встретятся.
Пример с BFS (поиск в ширину):
python
from collections import deque
def bidirectional_bfs(graph, start, end):
if start == end:
return [start]
# Очереди для прямого и обратного поиска
queue_start = deque([start])
queue_end = deque([end])
# Словари для хранения путей
parent_start = {start: None}
parent_end = {end: None}
while queue_start and queue_end:
# Шаг прямого поиска
current_start = queue_start.popleft()
for neighbor in graph[current_start]:
if neighbor not in parent_start:
parent_start[neighbor] = current_start
queue_start.append(neighbor)
if neighbor in parent_end: # Найдено пересечение
return reconstruct_path(parent_start, parent_end, neighbor)
# Шаг обратного поиска
current_end = queue_end.popleft()
for neighbor in graph[current_end]:
if neighbor not in parent_end:
parent_end[neighbor] = current_end
queue_end.append(neighbor)
if neighbor in parent_start: # Найдено пересечение
return reconstruct_path(parent_start, parent_end, neighbor)
return None # Путь не найденПреимущества:
- Эффективен для больших графов (сокращает время в 2 раза в лучшем случае).
- Работает быстрее одностороннего BFS, если граф симметричен.
Ограничения:
- Требует четко определенную конечную точку.
- Сложнее реализовать для взвешенных графов (например, Dijkstra).

Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
офферы быстрее!
Попробовать бесплатно
Следующий вопрос
Это единственный вопрос по вашему фильтру
как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы