Встречается на собеседованиях • сегодня

Что такое 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).
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы