Предсловие

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

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

1. Big O нотация: Формальный способ оценки сложности алгоритмов, который помогает понять, насколько эффективно они работают с увеличением объема данных. Подробнее читайте здесь и здесь.

2. Массивы: Основные структуры для хранения последовательных данных, их преимущества и недостатки. Подробнее читайте здесь.

3. Связные списки: Гибкие структуры данных, которые позволяют эффективно управлять памятью и изменять размер в процессе работы. Подробности и примеры использования можно найти здесь.

4. Стеки и очереди: Основные структуры данных для управления последовательностью выполнения операций и обработки данных в порядке их поступления или приоритетности. Узнайте больше здесь.

5. Хеш‑таблицы: Эффективный способ хранения и быстрого доступа к данным с помощью хеш‑функций. Статья доступна по ссылке.

6. Деревья и двоичные деревья поиска: Фундаментальные структуры данных для организации и поиска информации. Узнать больше можно здесь.

7. Алгоритмы сортировки: Ключевые методы упорядочивания данных, включая пузырьковую сортировку, сортировку слиянием, быструю сортировку и другие. Узнайте больше о подходах к сортировке по ссылке.

8. Ряд Фибоначчи и мемоизация: Применение динамического программирования и оптимизация вычислений при работе с рекурсивными задачами, такими как вычисление чисел Фибоначчи. Прочитать можно здесь.

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

Подписывайтесь на мой 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))

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

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

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

Заключение

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

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

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