Реализация поиска в ширину на PHP

В моих предыдущих статьях я рассмотрел некоторые аспекты поиска пути между узлами в графе.

В моем случае график представляет собой центр обработки данных с сетевыми устройствами и сетевыми кабелями, соединяющими их.

Оперативный персонал должен знать маршрут между своими устройствами и всеми кабелями на этом маршруте для целей обслуживания и инвентаризации.

Я уже показывал, как можно представить маршрут с помощью графа Санки или как мы можем извлечь данные о кабелях с помощью PHP и Laravel из системной базы данных.

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

Согласно его странице в Википедии Поиск в ширину (BFS) — это «алгоритм поиска в древовидной структуре данных для узла, который удовлетворяет данное свойство. Он начинается с корня дерева и исследует все узлы на текущей глубине, прежде чем перейти к узлам на следующем уровне глубины. Дополнительная память, обычно очередь, необходима для отслеживания дочерних узлов, которые были обнаружены, но еще не исследованы».

Моя реализация немного меняет это таким образом, что корень дерева является начальным устройством, а узел, который удовлетворяет заданному свойству (тема поиска), является моим конечным устройством.

Помимо этого, я попытался реализовать свою версию BFS как можно ближе к рекомендуемому псевдокоду.

Я создал класс Graph на PHP, который не только представляет структуру данных, но также содержит метод widthFirstSearch().

Класс может быть создан с помощью следующего конструктора:

public function __construct(protected array $graph = []) {
    $this->explored = $this->markAllNodesAsUnExplored();
}

Он берет граф, устанавливает для всех узлов неисследованные значения и сохраняет это состояние в частном свойстве.

После того, как мы построили наш объект Graph, мы можем вызвать его метод widthFirstSearch().

Нам необходимо указать корневой узел (начальное или исходное сетевое устройство), а также целевое устройство.

public function breadthFirstSearch(int $origin, int $destination) {

    $this->origin = $origin;
    $this->destination = $destination;

    $q = new SplQueue();

    $q->enqueue($origin);
    $this->setAsExplored($origin);

    $this->setParent(vertex: $origin, parent: $origin);

    while (!$q->isEmpty() && $q->bottom() != $destination) {
        $currentVertex = $q->dequeue();
        foreach ($this->adjacentEdges($currentVertex) as $vertex) {
            if (!$this->isExplored($vertex)) {
                $q->enqueue($vertex);
                $this->setAsExplored($vertex);
                $this->setParent(vertex: $vertex, parent: $currentVertex);
            }
        }
    }

    $this->setRoute($this->extractRoute());

    return $this;

}

Алгоритм довольно прост:

мы устанавливаем исходный узел как исследованный, помещаем его в очередь и устанавливаем его родительский узел (в нашем случае это он сам),
мы перебираем все соседние узлы (или вершины, чтобы придерживаться номенклатуры теории графов),
для каждого соседнего узла, если он еще не исследован, мы помещаем его в нашу SplQueue (устанавливаем в режим FIFO), устанавливаем узел в состояние исследован, а также регистрируем его родителя,
мы продолжаем описанный выше процесс, пока наша очередь не станет пустой

После того, как мы завершили процесс поиска, мы извлекаем маршрут между исходным и конечным узлами (если они были исследованы) с помощью метода extractRoute:

private function extractRoute(array $parents = []): array {

    $p = $parents ?: $this->parents;
    $route = [];

    if (isset($p[$this->destination])) {
        $route[] = $this->destination;
        $vertex = $p[$this->destination];
        while ($vertex !== $this->origin) {
            $route[] = $vertex;
            $vertex = $p[$vertex];
        }
        $route[] = $this->origin;
    }

    return array_reverse($route);

}

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

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

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

Временная сложность алгоритма BFS может быть выражена как

, так как в худшем случае будут исследованы каждая вершина и каждое ребро.

Реализация поиска в ширину на PHP

Вопросы по теме