Поиск в ширину — вопросы с собеседований

Поиск в ширину (Breadth-First Search, BFS) — это метод обхода графа или дерева, при котором сначала посещаются все соседние вершины, прежде чем переходить к вершинам следующего уровня. Если представить это в виде поиска по дереву, то сначала исследуются все «дети» корневой вершины, затем все «внуки», и так далее, пока не будут посещены все вершины или не будет найден нужный элемент.

Проще говоря, если вы находитесь в центре лабиринта и хотите найти выход, используя поиск в ширину, вы бы начали с исследования всех путей, которые ведут непосредственно от вас, затем проверили бы пути, идущие от концов этих путей, и так далее, пока не нашли бы выход.

Этот метод полезен, когда нужно найти кратчайший путь от одной точки к другой, потому что он сначала рассматривает ближайшие возможности.

Где используется поиск в ширину

Поиск в ширину используется в различных областях и задачах, где требуется нахождение кратчайшего пути или обход графа по уровням. Вот несколько примеров применения поиска в ширину:

• Нахождение кратчайшего пути в графе: Например, в сетевых топологиях для нахождения кратчайшего пути между двумя узлами.
• Алгоритмы маршрутизации: В сетевой инженерии для вычисления оптимальных маршрутов передачи данных.
• Поиск в социальных сетях: Для определения «уровня отношений» между двумя пользователями, например, чтобы найти, через сколько «рукопожатий» пользователи связаны друг с другом.
• Игры и головоломки: Для нахождения минимального количества ходов, необходимых для решения, например, в пятнашках или для определения возможности выигрыша в определенной конфигурации игрового поля.
• Анализ графов: В теории графов для определения компонент связности, то есть для проверки, все ли вершины графа достижимы из любой другой вершины.
• Алгоритмы параллельного программирования: Для разбиения задач на уровни, которые могут быть выполнены параллельно.
• Обработка данных в больших графах: Например, в базах данных графов для выполнения запросов, требующих обхода узлов по уровням.

Эти примеры демонстрируют широкий спектр применения поиска в ширину, от компьютерных наук до социальных сетей и за их пределами.

В чем отличие поиска в ширину от поиска в глубину

Поиск в ширину и поиск в глубину это два метода обхода графов и деревьев, но они работают по разным принципам.

Поиск в ширину начинает обход с корневой вершины (или указанной стартовой вершины), затем переходит к соседним вершинам, затем к их соседям и так далее. Это означает, что он сначала исследует все вершины на одном уровне, прежде чем перейти к вершинам следующего уровня. Этот метод обычно используется для нахождения кратчайшего пути в графе.

Поиск в глубину, с другой стороны, начинает обход с корневой вершины, а затем идет вглубь по каждой ветви, пока не достигнет конца или не встретит вершину, которую уже посетил. После этого он возвращается назад и продолжает исследование следующей ветви. Этот метод обычно используется для исследования всех возможных ветвей в графе.

В общем, можно сказать, что поиск в ширину идет «от корня ко всем листьям», а поиск в глубину — «от корня через каждую ветвь до конца».

Поиск в ширину на Swift

Вот простой пример алгоритма поиска в ширину на языке программирования Swift, который обходит узлы графа:

import Foundation

// Определяем класс для узла графа
class Node {
    var value: Int
    var neighbors: [Node]
    
    init(value: Int) {
        self.value = value
        self.neighbors = []
    }
    
    // Функция для добавления соседа к узлу
    func addNeighbor(node: Node) {
        neighbors.append(node)
    }
}

// Функция поиска в ширину
func breadthFirstSearch(startNode: Node) {
    var visited = Set<Node>() // Множество для хранения посещенных узлов
    var queue = [Node]() // Очередь для узлов, которые нужно посетить
    
    // Начинаем с узла startNode
    queue.append(startNode)
    
    while let currentNode = queue.first { // Пока очередь не пуста
        queue.removeFirst() // Извлекаем первый элемент из очереди
        visited.insert(currentNode) // Помечаем узел как посещенный
        print(currentNode.value) // Выводим значение узла
        
        // Добавляем все соседние узлы, которые еще не были посещены, в очередь
        for neighbor in currentNode.neighbors where !visited.contains(neighbor) {
            queue.append(neighbor)
        }
    }
}

// Пример использования
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
let node4 = Node(value: 4)
let node5 = Node(value: 5)

node1.addNeighbor(node: node2)
node1.addNeighbor(node: node3)
node2.addNeighbor(node: node4)
node3.addNeighbor(node: node4)
node4.addNeighbor(node: node5)

breadthFirstSearch(startNode: node1)

Этот код определяет класс Node для представления узлов в графе, каждый из которых имеет значение (value) и список соседей (neighbors). В функции breadthFirstSearch используется очередь для хранения узлов, которые нужно посетить, и множество для отслеживания посещенных узлов. Алгоритм начинается с узла startNode и продолжается до тех пор, пока в очереди есть узлы для посещения, добавляя соседние узлы в очередь, если они еще не были посещены.

Дополнительно

• 10 алгоритмов, которые должен изучить каждый разработчик
• Другие вопросы с собеседований