Содержание

• Вы научитесь моделировать сети при помощи новой абстрактной структуры данных – графов .
• Вы освоите поиск в ширину – алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к Х?»
• Вы узнаете, чем направленные графы отличаются от ненаправленных.
• Вы освоите топологическую сортировку – другой алгоритм сортировки, раскрывающий связи между узлами.

Что такое граф?

Граф моделирует набор связей. Представьте, что вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смоделировать так:

А полный граф может выглядеть так:

Алекс должен Раме, Том должен Адиту и т. д. Каждый граф состоит из узлов и ребер.

Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями. На этом графе Рама является соседом Алекса. С другой стороны, Адит соседом Алекса не является, потому что они не соединены напрямую. При этом Адит является соседом Рамы и Тома.
Графы используются для моделирования связей между разными объектами .
А теперь посмотрим, как работает поиск в ширину.

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

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

• тип 1: существует ли путь от узла А к узлу В?
• тип 2: как выглядит кратчайший путь от узла А к узлу В?

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

Сначала нужно построить список друзей для поиска.

Теперь нужно обратиться к каждому человеку в списке и проверить, продает ли этот человек манго.

Предположим, ни один из ваших друзей не продает манго. Теперь поиск продолжается среди друзей ваших друзей .

Со времен мы проверите всех ее друзей, а потом их друзей и т.д . С этим алгоритмом поиск рано или поздно пройдет по всей сети , пока вы все-таки не наткнетесь на продавца манго. Такой алгоритм и называется поиском в ширину.

Поиск кратчайшего пути

На всякий случай напомню два вопроса, на которые может ответить алгоритм поиска в ширину:

• тип 1: существует ли путь от узла А к узлу В? (Есть ли продавец манго в вашей сети?)
• тип 2: как выглядит кратчайший путь от узла А к узлу В? (Кто из продавцов манго находится ближе всего к вам?)

Удастся ли вам найти ближайшего продавца манго? Будем считать, что ваши друзья это связи первого уровня, а друзья друзей связи второго уровня.

Связи первого уровня предпочтительнее связей второго уровня, связи второго уровня предпочтительнее связей третьего уровня и т. д. Отсюда следует, что поиск по контактам второго уровня не должен производиться, пока вы не будете полностью уверены в том, что среди связей первого уровня нет ни одного продавца манго.

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

Следовательно, проверять связи нужно в порядке их добавления. Для операций такого рода существует специальная структура данных, которая называется очередью.

Очереди

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

Очередь относится к категории структур данных FIFO: First In, First Out («первым вошел, первым вышел»). А стек принадлежит к числу структур данных LIFO: Last In, First Out («последним пришел, первым вышел»).

Задача

Найдите длину кратчайшего пути от «саt» к «bat». воспользуйтесь поиском в ширину для ее решения.

dist – это просто сокращение от слова distance, то есть «расстояние».

В BFS так называют таблицу (или массив, или словарь), где мы храним: на каком расстоянии от старта находится каждая вершина.

Шаг 0. Инициализация

• Очередь (queue): [cab]
• dist(cab)=0
• visited: {cab}

Шаг 1. Достаём cab
cab на расстоянии 0.
Смотрим соседей cab (куда ведут стрелки): car, cat.

Отмечаем их:

• dist(car)=1, visited += car, в очередь
• dist(cat)=1, visited += cat, в очередь

Теперь:

• queue: [car, cat]
• dist: cab=0, car=1, cat=1

Шаг 2. Достаём car
car на расстоянии 1.
Соседи car: cat, bar.

• cat уже посещён (dist уже 1) – пропускаем
• bar ещё нет:
  dist(bar)=2, visited += bar, в очередь

Теперь:

• queue: [cat, bar]
• dist: cab=0, car=1, cat=1, bar=2

Шаг 3. Достаём cat
cat на расстоянии 1.
Соседи cat: mat, bat.

• mat ещё нет:
  dist(mat)=2, visited += mat, в очередь
• bat ещё нет:
  dist(bat)=2, visited += bat, в очередь

Теперь:

• queue: [bar, mat, bat]
• dist: cab=0, car=1, cat=1, bar=2, mat=2, bat=2

И вот тут ключевой момент BFS:
bat найден впервые с расстоянием 2 – это и есть кратчайшее расстояние, потому что BFS идёт слоями и раньше слоя 2 он физически не мог появиться.

Ответ
Длина кратчайшего пути от cab к bat = 2.

Кратчайший путь (один из):
cab -> cat -> bat

Для сравнения, путь через mat реально существует, но он длиннее:
cab -> cat -> mat -> bat (длина 3)

Так что mat мы не выкидываем – он просто не выигрывает.

Реализация графа

Для начала необходимо реализовать граф на программном уровне . Граф состоит из
нескольких узлов. И каждый узел соединяется с соседними узлами. Как выразить отношение типа «вы – > боб»? К счастью, вам уже известна структура данных, способная выражать отношения: хеш-таблица!

graph [ "you"] = [ "alice", ЬоЬ", "claire"]
graph("bob"] = ("anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph("jonny"] = []  

Реализация алгоритма

Все начинается с создания очереди.

Далее проходимся циклом.

А теперь посмотрим, как работает поиск в ширину.

И так далее . Алгоритм продолжает работать до тех пор, пока:

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

Важный момент:

У Алисы и Боба есть один общий друг: Пегги. Следовательно, Пегги будет добавлена в очередь дважды. Прежде чем проверять человека, следует убедиться в том, что он не был проверен ранее. Для этого мы будем вести список уже проверенных людей.

А вот окончательная версия кода поиска в ширину, в которой учтено это обстоятельство:

Реализация в PHP

Представь город, где каждая станция метро названа трёхбуквенным кодом:
cab, car, cat, mat, bar, bat.
Между станциями есть односторонние переходы. За один переход ты тратишь ровно одну минуту.

Схема переходов такая:

• из cab можно перейти в car и cat
• из car можно перейти в cat и bar
• из cat можно перейти в mat и bat
• из mat можно перейти в bat
• из bar можно перейти в bat

Ты находишься на станции cab и хочешь как можно быстрее попасть на станцию bat.

Нужно:

1. Найти минимальное количество переходов от cab до bat.
2. Восстановить сам маршрут, по которому ты пойдёшь.
3. Решить задачу алгоритмом поиска в ширину (BFS), потому что:
   • все переходы равны по «цене»
   • нужно именно кратчайшее число шагов, а не просто любой путь

В этой задаче смысл BFS именно в том, чтобы дойти до bat и понять, за сколько шагов это можно сделать минимально.

<?php

$graph = [
    'cab' => ['car', 'cat'],
    'car' => ['cat', 'bar'],
    'cat' => ['mat', 'bat'],
    'mat' => ['bat'],
    'bar' => ['bat'],
    'bat' => [],
];

function findFastWay(array $graph, string $start = 'cab', string $goal = 'bat'): array
{
    $queue = [];
    $visited = [];
    $dist = [];

    // старт
    $queue[] = $start; // "cab"
    $visited[$start] = true;
    $dist[$start] = 0;

    while (count($queue) > 0) {
        // достаем первый элемент очереди в переменную и удаляем его из массива очереди
        // В классическом BFS в очередь кладут сам старт, а не его 
        // соседей. Потому что BFS - это не «сразу прыгнуть на уровень 1»,
        // а распространяться волнами от источника.
        $current = array_shift($queue);

        // нашли цель
        if ($current === $goal) {
            return [
                'found' => true,
                'distance' => $dist[$current],
            ];
        }

        // обходим соседей
        foreach ($graph[$current] as $next) {
            if (isset($visited[$next])) {
                continue;
            }

            $visited[$next] = true;
            $dist[$next] = $dist[$current] + 1;
            $queue[] = $next;
        }

        var_dump($queue); // "car", "cat" на первой итерации
    }

    return [
        'found' => false,
        'distance' => null,
    ];
}

$result = findFastWay($graph);
var_dump($result);
// Output
array(2) {
  ["found"]=>
  bool(true)
  ["distance"]=>
  int(2)
}

BFS расширяет фронт поиска слоями:

• сначала все вершины на расстоянии 1
• потом все на расстоянии 2
• потом на расстоянии 3
• и т.д.

И в тот момент, когда bat впервые появляется,
мы знаем железно:

👉 это минимальное расстояние
👉 короче пути не существует в принципе

// Финальный вывод очереди по итерациям
// Start
array(1) {
  [0]=>
  string(3) "cab"
}
// Go deeper
array(2) {
  [0]=>
  string(3) "car"
  [1]=>
  string(3) "cat"
}
array(2) {
  [0]=>
  string(3) "cat"
  [1]=>
  string(3) "bar"
}
array(3) {
  [0]=>
  string(3) "bar"
  [1]=>
  string(3) "mat"
  [2]=>
  string(3) "bat"
}
array(2) {
  [0]=>
  string(3) "mat"
  [1]=>
  string(3) "bat"
}
array(1) {
  [0]=>
  string(3) "bat"
}