Реализация и изучение графов в Swift

Использование расширенных структур данных

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

В этом руководстве мы кратко познакомимся с тем, что такое графики, и рассмотрим некоторые из их свойств. Далее мы рассмотрим, как реализовать графики в Swift и использовать их в наших проектах. Для этого мы будем использовать фреймворк SwiftGraph, который позволяет нам легко создавать графы, перемещаться по ним с помощью различных алгоритмов и анализировать их структуру.

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

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

Графы могут быть направленными, что означает, что все ребра между двумя вершинами имеют направление и указывают от одной вершины к другой. Если это не так, мы называем этот граф неориентированным. Пример неориентированного графа - друзья в Facebook. Однако подписчиков в Twitter можно представить в виде ориентированного графа.

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

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

Есть и другие свойства графика, которые вы можете изучить, но пока этого достаточно. Напишем код!

Как мы можем использовать графики в Swift?

Давайте посмотрим, как использовать графики в наших приложениях. К счастью, нам не нужно самостоятельно реализовывать вершины и ребра. Мы можем использовать фреймворк под названием SwiftGraph. Он предоставляет протоколы, структуры и классы для моделирования графов. Он также предоставляет функции для их изучения, такие как поиск кратчайшего пути между двумя узлами или обнаружение циклов.

SwiftGraph определяет протокол Edge, которому требуется свойство для исходной и конечной вершин, называемое u и v, а также логическое значение directed для различения направленных и неориентированных ребер. Этот протокол реализуется двумя структурами: UnweightedEdge и WeightedEdge.

Кроме того, эта структура предоставляет протокол Graph, который реализуется двумя классами UnweightedGraph и WeightedGraph. Среди прочего, протокол определяет инициализатор, который принимает массив вершин, и функцию addEdge, которая принимает ребро и логический флаг, независимо от того, направлен он или нет. В этом протоколе определено несколько вычисляемых свойств и функций, например для доступа к вершинам и ребрам по индексу, проверки, содержится ли вершина в графе, добавления вершин и ребер и многого другого. Вы можете найти все функции в подробной документации SwiftGraph.

Давайте посмотрим на небольшой пример невзвешенного графика, в котором мы создаем график из Person объектов, представляющих дружбу, и находим общего друга двух людей:

// 1 - Сначала мы определяем структуру Person. Каждый человек состоит из имени и фамилии.

// 2. Теперь мы создаем три объекта-примера: john, jane и max.

// 3. Мы используем класс UnweightedGraph SwiftGraph для создания графика из Person объектов. Мы передаем трех человек, которых мы создали ранее, как его вершины. Кроме того, мы добавляем два ребра, одно от john до jane, что означает, что Джон и Джейн друзья, и одно от john до max.

// 4 - Если мы хотим найти общего друга Джейн и Макса, нам нужно найти существующий путь между этими двумя вершинами. Вызывая функцию поиска bfs(from:to:) на этом графе, мы можем найти массив ребер между начальной и конечной вершинами. В этом случае будет два ребра: одно от Макса к Джону и одно от Джона к Джейн. Таким образом, у этих двоих действительно есть общий друг.

В дополнение к UnweightedGraph и WeightedGraph эта структура предоставляет три специальных графа: так называемый StarGraph, который имеет одну центральную вершину с несколькими ребрами, идущими к другим вершинам вокруг центра, CompleteGraph, в котором все вершины соединены со всеми остальными вершинами, и UniqueElementsGraph, который содержит только уникальные ребра и не содержит пары равных вершин. В то время как первые два являются только невзвешенными, последний тип графика может быть как взвешенным, так и невзвешенным.

Как мы можем исследовать график?

Итак, теперь, когда мы знаем, как создать граф и добавить вершины и ребра, что мы можем с ним делать?

Перемещение по графику

В предыдущем примере мы уже использовали метод bfs(from:to:) на графах, чтобы найти путь между двумя узлами. Это сокращение означает поиск в ширину, что означает, что алгоритм поиска сначала просматривает все окружающие вершины текущего узла, а затем обрабатывает каждый из этих узлов таким же образом. Альтернативный подход - поиск в глубину, который мы можем использовать, вызвав dfs(from:to:). При использовании этого алгоритма сначала следует путь до его конца, а затем посещается новая ветвь графа.

Давайте посмотрим на простой пример, который можно увидеть на картинке ниже. Для следующего графа с узлами от A до G, если мы выполним на нем bfs, мы ищем все вершины, которые связаны с A, таким образом, мы находим B, затем C и, наконец, D. Теперь мы повторяем это с каждым найденным узлом. в том порядке, в котором они были найдены. Поскольку E и F соединены с B, они будут следующими вершинами, которые нужно обнаружить. C не имеет исходящего ребра, и поэтому больше нет узлов. Наконец, G находится путем поиска соседей D. Порядок обнаружения узлов: A, B, C, D, E, F и G.

Используя dfs на том же графе, мы проследим первое соединение, исходящее от A к B. Теперь, вместо того, чтобы начинать заново с A, мы посмотрим на каждое ребро, выходящее из вершины B, и, таким образом, мы найдем E, а затем F. Далее , поскольку все вершины ниже B уже обнаружены, мы начнем снова с A со следующим ребром, идущим к C. Поскольку C не имеет исходящих ребер, кроме одного, идущего к A, мы посмотрим на последнее ребро из A. Там мы найдет D и, наконец, G. Порядок обнаружения узлов: A, B, E, F, C, D и G.

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

Обнаружение циклов

SwiftGraph предоставляет два метода для проверки наличия циклов в данном графике: detectCycles(upToLength:) и detectCyclesAsEdges(upToLength:). Оба основаны на алгоритме, представленном в этой статье. Первый возвращает цикл, представленный списком вершин, второй - списком ребер. Параметр upToLength по умолчанию равен Int.max, поэтому его можно не указывать.

Примечание. Для получения правильных результатов важно добавлять направленные края.

Вот пример того, как использовать эти методы:

// 1 - Создаем новый график с друзьями. На этот раз Джон - друг Джейн, Джейн - друг Макса, а Макс - друг Джона - вы можете ясно видеть цикл! Но, как отмечалось выше, мы устанавливаем directed в значение true для каждого из ребер.

// 2 - Используя detectCycles, мы можем найти все вершины цикла. Результатом является массив, содержащий четыре узла: Джон, Джейн, Макс и снова Джон. Поскольку мы хотим найти все циклы независимо от их размера, мы опускаем значение параметра upToLenght.

// 3 - Когда нас интересуют ребра, образующие цикл, а не вершины, мы можем использовать detectCyclesAsEdges. В этом примере мы получим массив, содержащий ребра от элемента 0 до 1, от 1 до 2 и от 2 до 0. Опять же, мы опускаем ограничение циклической длины.

Сортировка вершин графа

Вы даже можете отсортировать все вершины графа так, чтобы одна вершина имела меньшее положение, чем другая, - если граф содержит ребро от первого до второго. Но это возможно только для ориентированных ациклических графов (DAG). Такая сортировка называется топологической сортировкой.

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

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

В этом руководстве мы увидели, как создавать и использовать графики в SwiftGraph. Мы исследовали различные виды графов и то, как найти связь между двумя узлами с помощью bfs и dfs. Мы узнали, как определять циклы, и, наконец, что такое топологическая сортировка и как ее использовать.

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

Графики могут быть очень полезны для моделирования сложных сетей и соединений. Если вы собираетесь использовать их в своем приложении, SwiftGraph - отличная платформа для этого. Он обеспечивает удобный способ объявления и создания различных видов графиков и имеет мощные функции для работы с ними. Кроме того, он хорошо задокументирован и протестирован.

Если вы хотите узнать больше о графах и узнать, как реализовать их самостоятельно в Swift, ознакомьтесь со статьей Райвендерлиха Графы со списком смежности.

Ресурсы