8.5. Основы Kotlin. Графы

Перегрузка операторов

Рассмотрим теперь вот это определение:

Ключевое слово operator в определении означает, что данная функция переопределяет (перегружает) работу того или иного оператора. Конкретный оператор в Котлине привязывается к названию функции. Функции get соответствует оператор индексации, то есть, имея граф g, мы сможем достать у него вершину по имени с помощью g[name].

В теле функции мы обращаемся к карте vertices, получая из неё Vertex?. Далее вновь используется Элвис-оператор, в правой части которого генерируется исключение, прекращающее работу функции. Это означает, что данная функция, вместо того чтобы вернуть null в случае, когда соответствующего ключа нет в карте, бросает исключение IllegalArgumentException. Зато результат функции становится Vertex (без ?).

Следующий фрагмент использует перегруженный оператор индексации:

Данная функция вызывает другую функцию connect — с параметрами типа Vertex вместо String. Для преобразования имени вершины first к самой вершине используется this[first]this здесь — ключевое слово (этот), обозначающее граф-получатель, то есть тот граф, для которого вызвана функция connectthis[first] вместе использует индексацию на графе.

Поиск на графе

Алгоритмы поиска на графе могут иметь различную цель. Мы рассмотрим их на примере определения расстояния между вершинами. Расстояние между вершинами A и B на графе определяется как минимальное число рёбер, по которым нужно пройти для того, чтобы попасть из A в B. См. пример:

512px Shortest path.svg

Здесь расстояние между вершинами A и B равно 1, между A и E — 2, между C и F — 3.

Для определения расстояния нужно в том или ином порядке рассмотреть все цепочки рёбер, начинающихся в вершине A, найти те из них, которые заканчиваются в B и определить самую короткую цепочку. Есть два варианта рассмотрения таких цепочек — поиск в глубину и поиск в ширину.

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

Поиск в ширину идёт «волнами». Вначале мы перебираем всех соседок вершины A, запоминая расстояние до каждой из них (1). Затем мы перебираем всех соседок соседок вершины A, имея уже расстояние в 2 ребра. Затем происходит перебор вершин на расстоянии 3 и так далее, пока мы не уткнёмся в вершину B.

Реализация поиска в глубину

DFS = Depth-First Search.

Поиск в глубину обычно реализуется рекурсивно, с использованием следующих правил:

  1. Расстояние от любой вершины до самой себя равно 0.
  2. Пусть N(A) — все вершины, соседние с A. Тогда distance(A, B) = min(distance(N, B)) + 1, где минимум выбирается среди всех вершин N, входящих в N(A).

Наивная реализация этих правил могла бы выглядеть вот так:

Предполагается, что результат этой функции равен null при отсутствии соединения между вершинами (например, если у стартовой вершины нет соседей). Функция высшего порядка mapNotNull при этом вызывает dfs на всех соседях и фильтрует получаемые результаты, удаляя из них все значения, равные null. Вызов mapNotNull в данном случае эквивалентен последовательности вызовов map { dfs(it, finish) }.filterNotNull().

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

Именно поэтому в функцию было введено множество уже посещённых вершин (третьим параметром, изначально он пуст). Уже посещённые вершины исключаются из множества соседей с помощью filter { it !in visited }, а при рекурсивном вызове функции в это множество добавляется только что посещённая вершина. Это обеспечивает конечность работы функции поиска.

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

BFS = Breadth-First Search.

В процессе выполнения поиска в ширину мы используем очередь вершин ArrayQueue<Vertex>. Принцип функционирования очереди подобен настоящей очереди в магазине — вызов функции queue.add добавляет вершину-аргумент в конец очереди (увеличивая размер очереди на 1), а вызов функции queue.poll, наоборот, достаёт из головы очереди первую вершину (уменьшая размер на 1). Для пустой очереди результат queue.poll будет равен null. Изначально в очередь записывается только стартовая вершина.

Для хранения найденных расстояний до уже посещённых вершин функция использует ассоциативный массив, ключом в котором является вершина, а значением — расстояние до неё. Изначально нам известно, что расстояние от стартовой вершины до неё же равно 0.

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

Обратите внимание на оператор val distance = visited[next]!!. Здесь visited[next] обращается по индексу к ассоциативному массиву и имеет результат Int? (Int или null). Мы же хотим получить просто Int. Поскольку в функции постановка вершины в очередь и запись расстояния для неё выполняются всегда друг за другом, мы уверены, что по данному индексу в массиве имеется какое-то значение. Поэтому мы можем применить оператор !!для преобразования типа из Int? в Int. Если всё же окажется, что значения по данному индексу в массиве нет, в этом месте произойдёт исключение KotlinNullPointerException.

/9-osnovy-kotlin-klassy-i-interfejsy/
Добавить комментарий