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

333px 6n graf.svg

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

086 01

Структуры данных, подобные графам, могут возникать в различных задач поиска оптимального решения. Например, в lesson8/task2 имеется задача о поиске наиболее короткой траектории движения шахматного коня. Эту задачу можно описать с помощью графа, вершинами которого являются клетки шахматной доски, а рёбра соединяют те из них, между которыми может двигаться шахматный конь. Такой граф может выглядеть примерно так:

1024px Knight%27s graph showing number of possible moves.svg

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

Описанный здесь Graph является довольно сложным классом. Он включает в себя функцию addVertex (добавить вершину) и две функции connect (соединить) с разным набором параметров, причём одна из них является закрытой(private). Для доступа к списку вершин, соседних для данной, в классе имеется функция neighbors, Кроме этого, в классе имеется операторная функция get, которая также является закрытой, свойство (val) vertices (вершины), в котором хранится ассоциативный массив (MutableMap) и которое опять-таки закрыто, и вложенный класс Vertex(вершина) со свойствами name (имя) и neighbors (соседи). Рассмотрим все эти элементы класса Graph подробнее.

Члены класса

Класс может иметь произвольное количество членов (members), которые делятся на две категории: свойства и функции. Свойства класса определяются как val (неизменяемые) или var (изменяемые). Чаще всего они используются для описания внутренней структуры класса; например, в классе Graph свойство vertices используется для сохранения информации о вершинах графа, а в классе Vertex свойство neighbors сохраняет информацию о вершинах, соседних (то есть соединённых ребром) с данной.

Функции класса определяются как fun и используются для различных операций с объектом данного класса, в данном случае — с графом. В данном случае, функции connect служат для соединения двух вершин графа ребром — то есть, для добавления в граф нового ребра. Функция addVertex добавляет в граф новую вершину.

Видимость

Члены класса могут иметь различную видимость. Чаще всего в Котлине используются два уровня видимости: открытый (public, по умолчанию) и закрытый (private). Для изменения уровня видимости следует указать ключевое слово public или private перед определением члена класса.

Открытые члены класса могут использоваться всеми. В любой части программы мы имеем право написать graph.connect(…​) для добавления в граф нового ребра. Закрытые члены класса могут использоваться только самим классом; при попытке написать graph.vertices снаружи класса для обращения к свойству vertices произойдёт ошибка при компиляции программы.

Закрытые члены класса были придуманы программистами, чтобы разграничить ответственность за разные участки программы. Действует следующий принцип: каждый класс сам отвечает за своё содержимое. В идеале, никакие операции с открытыми членами класса не должны приводить к ошибкам, и состояние объекта класса должно меняться в соответствии с выполненными операциями. Например:

Программист, написавший функцию useGraph, резонно ожидает, что после выполнения приведённого кода в графе g будет четыре вершины и три ребра, выглядяющих примерно так, как изображено в комментарии. Он также ожидает, что при поиске вершин, соседних с «B», мы получим список из вершин «C» и «D». При этом ассоциативный массив vertices (который фактически и хранит информацию о вершинах графа), является закрытым и его не может изменять никто, кроме других членов данного класса.

Использованный здесь принцип программисты называют инкапсуляцией. Граф в данном случае подобен капсуле, на которой есть кнопки «addVertex» и «connect» (их нажатие изменяет граф), а также индикатор neighbors (вызов соответствующей функции не изменяет граф). Всё остальное находится внутри капсулы и не видно снаружи; закрытое содержимое графа является его личным (приватным) делом.

Вложенные классы

Довольно часто бывает так, что некоторый класс не имеет смысла без какого-то другого класса. Так произошло и в нашем примере — вершина не имеет никакого смысла без графа. В этом случае класс Vertex, соответствующий вершине, определяется внутри класса Graph. Поскольку в данном случае класс закрытый, то и использоваться он может только внутри класса Graph. Если бы класс Vertex был открыт, его можно было бы использовать снаружи графа как Graph.Vertex.

В данном случае вершина имеет свойство «имя» (name), которое задаётся в её конструкторе, и свойство «соседи» (neighbors), которое хранит мутирующее множество (MutableSet) из других вершин. При создании вершины множество её соседей пусто, но вызовы функции connect из графа расширяют его.

Множества и списки

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

Для множества имеется возможность проверить наличие в нём определённого элемента, или же перебрать все элементы множества с помощью цикла for — обе эти возможности есть и у списков. Для множества имеется свойство size и функции isEmpty()isNotEmpty() для определения его размера. Множества можно складывать друг с другом — все перечисленные операции у списков тоже имеются. Множества в Котлине бывают обычными Set<T> либо мутирующими MutableSet<T>.

Является ли множество просто списком, в котором нет одинаковых элементов? Нет, это не так. Множество не поддерживает доступ по индексу, то есть в нём отсутствует операция set[i] — как для чтения, так и для записи. Зато множество умеет значительно быстрее списка определять наличие в нём элементов element in set. Для реализации этой операции над списком необходимо перебрать его весь, а множества имеют более сложную структуру, позволяющую находить элементы в нём быстрее.

Создаются множества в Котлине с помощью функций setOf(…​) и mutableSetOf(…​).

Коллекции

Коллекция является так называемым надтипом как множества, так и списка. Коллекция объединяет их общие свойства и возможности. Список, помимо возможностей коллекции, имеет возможность индексирования. Множество, помимо возможностей коллекции, не добавляет в себя уже имеющиеся элементы.

Коллекция Collection<T> хранит в себе однотипные элементы типа T. Возможностями коллекции являются:

  1. Определение количества элементов (размера), пустоты, непустоты.
  2. Определение вхождения элемента и перебор элементов (in).
  3. Сложение с другой коллекцией или с отдельным элементом.
  4. Для мутирующей коллекции MutableCollection<T>, также — добавление и удаление элемента.

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

Ассоциативные массивы (карты)

Ассоциативный массив (он же — карта или словарь) Map<K, V> подобен обычному массиву или, вернее, списку. Разница заключается в том, что индексом в списке является целое число от 0 до list.size - 1, а индексом в ассоциативном массиве может быть всё что угодно. Тип используемого индекса (ключа) определяется параметром карты K, а тип хранимых значений — параметром V. Для массива vertices, ключом является строка String (имя вершины), а значением — сама вершина Vertex.

Класс Graph использует только две операции над vertices — создание и индексацию. Для создания карты используются метод mapOf(…​) для обычной карты Map<K, V>, либо mutableMapOf(…​) для мутирующей карты. Пример вызова:

Такой вызов создаст карту типа Map<String, Int>, ключом которой является строка, а значением — целое число. По ключу «John» карта хранит число 87 и так далее. Функция key to value создаёт пару из ключа и значения, а из перечисления пар создаётся сама карта.

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

Любопытно поведение карты при обращении по несуществующему ключу, например, map["Tom"] для карты из примера. В отличие от списка, никаких исключений при этом не формируется; однако, результат данной операции — null. Это так называемая нулевая ссылка, которая уже встречалась нам в шестом уроке. Тип результата операции обращения по индексу в данном случае Int?, что означает Int либо null.

Безопасные операции

Рассмотрим теперь подробнее функцию neighbors() из класса Graph:

Разберём определение этой функции. Как уже говорилось выше, результат vertices[name] может оказаться нулевой ссылкой, тип этого выражения Vertex?. У типа Vertex (без ?) имеется свойство neighbors; однако, обратиться к нему просто как vertices[name].neighbors нельзя, так как null не имеет ни свойств, ни методов. Поэтому приходиться использовать так называемое безопасное обращение: vertices[name]?.neighbors. Результатом такого обращения будет значение свойства neighbors у полученной из карты вершины; если же ключа name в карте нет, то вместо вершины мы будем иметь null и результатом безопасного обращения также будет null. Тип выражения vertices[name]?.neighbors — MutableSet<Vertex>?.

В дальнейшем мы тем же способом вызываем функцию высшего порядка map, замещая каждую вершину из полученного множества её именем и получая список имён. Поскольку обращение к map тоже происходит через ?., то при отсутствии найденной вершины с самого начала вместо списка имён мы получим null. Тип выражения vertices[name]?.neighbors?.map { it.name } — List<String>?.

Наконец, в конце выражения используется так называемый Элвис-оператор. Элвис-оператор имеет два аргумента, например, a ?: b и действует так:

  1. Если a не null, результат Элвис-оператора равен a.
  2. Если a null, результат Элвис-оператора равен b.

В примере с neighbors и в том и в другом случае мы имеем результат типа List<String>, поэтому и данная функция имеет тип результата List<String>.

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

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

Ключевое слово 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.

Добавить комментарий