Графы в Swift: Поиск в Глубину и Поиск в Ширину

Предсловие

Добро пожаловать в финальную статью цикла, посвященного структурам данных для iOS-разработчиков! На протяжении нескольких лет мы подробно рассматривали основные структуры данных, которые помогают эффективно решать задачи программирования и обработки данных. Сегодня мы завершаем этот цикл обзором графов и методов поиска в ширину (BFS) и поиска в глубину (DFS). Эти алгоритмы являются важной частью многих приложений, от поиска кратчайшего пути до анализа связности графов и многих других задач.

В этом цикле мы уже изучили:

Big O нотация: Формальный способ оценки сложности алгоритмов, который помогает понять, насколько эффективно они работают с увеличением объема данных. Подробнее читайте здесь и здесь.
Массивы: Основные структуры для хранения последовательных данных, их преимущества и недостатки. Подробнее читайте здесь.
Связные списки: Гибкие структуры данных, которые позволяют эффективно управлять памятью и изменять размер в процессе работы. Подробности и примеры использования можно найти здесь.
Стеки и очереди: Основные структуры данных для управления последовательностью выполнения операций и обработки данных в порядке их поступления или приоритетности. Узнайте больше здесь.
Хеш-таблицы: Эффективный способ хранения и быстрого доступа к данным с помощью хеш-функций. Статья доступна по ссылке.
Деревья и двоичные деревья поиска: Фундаментальные структуры данных для организации и поиска информации. Узнать больше можно здесь.
Алгоритмы сортировки: Ключевые методы упорядочивания данных, включая пузырьковую сортировку, сортировку слиянием, быструю сортировку и другие. Узнайте больше о подходах к сортировке по ссылке.
Ряд Фибоначчи и мемоизация: Применение динамического программирования и оптимизация вычислений при работе с рекурсивными задачами, такими как вычисление чисел Фибоначчи. Прочитать можно здесь.

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

Подписывайтесь на мой Telegram-канал!

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

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

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

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

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

Когда мы говорим о ребрах, существует два типа. Тип, который мы видели в бинарном дереве, – это направленное ребро, которое идет в одном направлении от одной вершины к другой. Но здесь, с обычными графами, мы не ограничены этим. Эти ребра могут быть двунаправленными, то есть идти в обоих направлениях. Кроме того, наши вершины могут соединяться с любой другой вершиной, как мы захотим. Мы не обязаны идти только от родителя к ребенку.

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

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

Сначала мы изучим три разных способа, которыми можно представлять графы как данные. Затем мы рассмотрим два наиболее распространенных способа использования этих структур данных для поиска в графах.

Как работают графы?

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

Начнем со списка ребер. В списке ребер мы просто берем каждое ребро в графе, например, от нуля до единицы, и представляем его как два элемента в массиве: ноль и один. В этом и заключается вся суть списка. Прелесть списка в его простоте. Нет ничего сложного в его представлении. Единственным недостатком является то, что если нам нужно найти конкретное ребро в списке, это будет линейный поиск, и нам придется искать по всему списку, другими словами, O(n).

С другой стороны, матрица смежности имеет очень быстрое время поиска. Здесь мы берем каждое ребро в графе и представляем его как единицу в двумерной матрице. Например, если ребро идет от нуля до единицы, ноль будет нашим элементом i, а один – элементом j. Мы найдем это место в матрице и поставим там единицу. То же самое для ребра от одного до двух: мы найдем место в матрице и вставим единицу в позиции один, два, чтобы представить это ребро. Преимущество матрицы смежности заключается в том, что она обеспечивает быстрый поиск O(1). Единственный недостаток заключается в том, что она не самая эффективная с точки зрения использования памяти. Если у нас мало ребер, в матрице будет много нулей, что приведет к потере памяти.

Но существует структура данных, которая сочетает простоту списка ребер со скоростью матрицы смежности, – это список смежности. В этой структуре мы берем каждую вершину и просто записываем каждого её соседа в виде списка в массиве. Например, вершина 0 имеет двух соседей: вершины 1 и 4. Мы просто сохраняем 1 и 4 в массиве, и это будут соседи вершины 0. Аналогично для вершины 1, у которой есть сосед 2. Вершина 2 не имеет соседей. Вершина 3 имеет двух соседей: 1 и 2, а вершина 4 имеет трёх соседей. Хранение массива массивов или связанных списков с этими элементами позволяет быстро создать коллекцию соседей для каждой вершины и затем быстро их находить.

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

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

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

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

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

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

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

Поиск в ширину в основном заключается в ведении учета. Мы отслеживаем, какие узлы мы посетили, пока обходим граф. Чтобы оставаться на верхнем уровне и посещать ближайших соседей, а не углубляться, мы используем очередь. Очереди работают по принципу FIFO (first in, first out). Очередь является основой алгоритма поиска в ширину: мы добавляем узлы, которые хотим посетить, в один конец очереди и извлекаем их в порядке поступления из другого конца. Так мы поддерживаем поиск в ширину. Давайте посмотрим, как это выглядит в коде.

import Foundation  // Очередь для поиска в ширину struct Queue<T> {     private var array: [T]          init() {         array = []     }          var isEmpty: Bool {         return array.isEmpty     }          var count: Int {         return array.count     }          mutating func add(_ element: T) {         array.append(element)     }          mutating func remove() -> T? {         if isEmpty {             return nil         } else {             return array.removeFirst()         }     }          func peek() -> T? {         return array.first     } }   // Стек для поиска в глубину struct Stack<T> {     fileprivate var array = [T]()          var isEmpty: Bool {         return array.isEmpty     }          var count: Int {         return array.count     }          mutating func push(_ element: T) {         array.append(element)     }          mutating func pop() -> T? {         return array.popLast()     }          var top: T? {         return array.last     } }  class Graph {     var V = 0                       // количество вершин     var adj = [[Int]]()             // список смежности          init(_ V: Int) {         self.V = V         for _ in 0..<V {             adj.append([Int]())  // создать пустой массив списков смежности         }     }          func addEdge(v: Int, w: Int) {         adj[v].append(w)     }         // Обход в ширину (BFS) от заданной начальной вершины s     func BFS(s: Int) -> [Int] {                  var result = [Int]()                  // Отметить все вершины как не посещенные         var visited = adj.map { _ in false }                  // Создать очередь для обхода в ширину (BFS Queue)         var queue = Queue<Int>()                   // Отметить первую вершину как посещенную и добавить в очередь         visited[s] = true         print("Starting at \(s)")         queue.add(s)         result.append(s)                  while queue.count > 0 {             let current = queue.remove()!             print("De-queueing \(current)")                      // Получить все смежные вершины текущей вершины         // Если смежная вершина еще не посещена,         // отметить её как посещенную и добавить в очередь                                   for n in adj[current] {                 if visited[n] == false {                     visited[n] = true                     print("Queuing \(n)")                     queue.add(n)                     result.append(n)                 }             }          }                  return result     }          // Обход в глубину (DFS) от заданной начальной вершины s     func DFS(s: Int) -> [Int] {                  var result = [Int]()                  // Отметить все вершины как не посещенные         var visited = adj.map { _ in false }                  // Создать стек для обхода в глубину (DFS Stack)         var stack = Stack<Int>()              // Отметить первую вершину как посещенную и добавить в стек //    print("Начало с вершины \(s)")         visited[s] = true         stack.push(s)                  while stack.count > 0 {             let current = stack.pop()! //        print("Извлечение из стека \(current)")             result.append(current)                  // Перебрать всех соседей, добавляя их в стек и извлекая по мере углубления         for n in adj[current] {             for n in adj[current] {                 if visited[n] == false {                     visited[n] = true //                print("Добавление в стек - \(n)")                     stack.push(n)                 }             }         }                  return result     } }  // Нужно создать столько вершин, сколько есть рёбер let g = Graph(8) g.addEdge(v: 0, w: 1) g.addEdge(v: 1, w: 4) g.addEdge(v: 4, w: 6) g.addEdge(v: 6, w: 0) g.addEdge(v: 1, w: 5) g.addEdge(v: 5, w: 3) g.addEdge(v: 3, w: 0) g.addEdge(v: 5, w: 2) g.addEdge(v: 2, w: 7)  //g.BFS(s: 0) print(g.DFS(s: 0))

Разбор кода

Первое, что мы сделаем, это создадим граф. Мы укажем, сколько узлов или вершин у нас есть в графе. В нашем случае это число будет восемь, тот же граф, который мы использовали ранее, от 0 до 7. И чтобы настроить это, нам нужно определить все ребра в нашем графе.

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

Когда мы готовы к поиску, мы просто вызываем функцию поиска в ширину, начиная с узла 0. И если мы запустим его, мы получим тот же результат, который видели ранее: начиная с узла 0, проходя в ширину до узла 7.

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

Когда мы создаем граф, мы просто знаем, сколько у нас вершин. Затем мы создаем наш список смежности, и мы готовы к работе. Для любой вершины V, соединенной с другой W, мы просто находим массив и добавляем эту другую вершину как соседа.

Когда дело доходит до обхода, начинаем с того, что помечаем все посещенные узлы как ложные(false), что означает, что мы еще не посетили ни одного узла. Затем мы создаем нашу очередь, чтобы отслеживать, где мы были. Берем первый узел, переданный в функцию поиска в ширину. Мы помечаем его как посещенный, выводим его, чтобы показать, что мы там были, и добавляем его в очередь. В нашем случае это будет узел 0.

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

Итак, это в двух словах, как работает поиск в ширину. Элегантный маленький алгоритм, абсолютно красивый. Теперь у вас есть пример, с которым можно поработать и поиграть самостоятельно.

Поиск в глубину

Поиск в глубину работает очень похоже на поиск в ширину. Здесь у нас тот же граф, который мы использовали в поиске в ширину, но обратите внимание, что теперь у нас есть стек вместо очереди. Помните, что в стеке используется принцип LIFO (last in, first out) — последнее вошедшее значение выходит первым. Это позволяет нам идти вглубь, а не вширь. Это и есть разница между поиском в глубину и в ширину.

Теперь давайте посмотрим, как это выглядит в коде.

Разбор кода

Код для поиска в глубину практически такой же, как и для поиска в ширину. Единственное отличие здесь в том, что вместо очереди у нас используется стек. И вместо добавления в очередь и извлечения из нее мы добавляем и извлекаем элементы из стека. Помимо этого, это тот же самый алгоритм.

У нас есть тот же тест с тем же графом. Если мы запустим его и посмотрим, мы увидим, что вместо обхода вширь мы идем вглубь. Итак, как в нашем примере, первый путь, который мы проходим, это от 0 до 3, затем до 5, затем до 2 и до 7. Затем мы возвращаемся и берем оставшийся путь: 6, 4 и 1.

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

Мы начинаем с узла 0. Мы заходим туда, посещаем его, добавляем в стек и помечаем его как посещенный. Теперь мы готовы идти дальше. Мы извлекаем узел 0 из стека. Первое, что мы делаем, это смотрим на его соседей: у нас есть узлы 1, 6 и 3. Мы добавляем их в стек в произвольном порядке, так как 3 был последним добавленным элементом, мы извлекаем его первым и смотрим на его соседей. У нас есть узел 5, поэтому мы помечаем его как посещенный, добавляем в стек и продолжаем к узлу 5.

Когда мы достигаем узла 5, мы осматриваемся и видим, что все узлы уже посещены, за исключением узла 2. Поэтому мы добавляем узел 2 в стек и продолжаем к нему. Мы извлекаем узел 2, смотрим на его соседей и видим, что узел 7 — единственный непосещенный узел. Мы помечаем его как посещенный, добавляем в стек, и на этом этапе путь заканчивается.

Обратите внимание на путь, который мы прошли: от 0 до 3, затем до 5, затем до 2 и до 7. Это поиск в глубину. Вместо того чтобы оставаться наверху и посещать узлы 1, 6 и 3 от узла 0, мы выбрали узел 3 и углубились как можно дальше по этому пути, пока не достигли узла 7.

Когда этот путь исчерпан, мы возвращаемся и видим, что следующий элемент в нашем стеке — это узел 6. Теперь мы берем другой путь, извлекаем узел 6, переходим к нему, осматриваемся и видим, что у нас есть непосещенный узел 4. Мы помечаем его как посещенный, добавляем в стек и продолжаем к узлу 4. Достигнув узла 4, мы видим, что у нас больше нет непосещенных узлов. Мы уже пометили узел 1 как посещенный. Теперь мы извлекаем узел 4, затем узел 1, и на этом всё. Мы просто выбрали другой маршрут для последнего участка пути, идя от узла 0 к узлу 6, затем к узлу 4 и, наконец, к узлу 1.

Заключение

Один из самых распространенных вопросов на собеседованиях, когда дело касается графов, — какой из алгоритмов лучше: поиск в ширину или поиск в глубину? И чтобы помочь вам ответить на этот вопрос, полезно иметь несколько ключевых примеров каждого из них в голове, чтобы вы могли объяснить, что ответ на этот вопрос зависит от контекста.

Например, вы можете сказать, что поиск в ширину лучше всего подходит для нахождения объектов, находящихся на верхних уровнях графа. Когда мы используем поиск в ширину, мы ищем ближайших соседей, что-то поблизости. Это включает в себя такие вещи, как социальные сети, такие как Facebook и LinkedIn, где нужно находить новых друзей, компьютерные игры, и все, где вы думаете, что решение задачи, которую вы ищете в графе, находится рядом или на вершине структуры графа. В таких случаях вы будете использовать поиск в ширину.

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

ссылка на оригинал статьи https://habr.com/ru/articles/845194/