Структуры графических данных невероятно важны и существуют в приложениях, которые мы используем ежедневно! Вспомните Google Maps, Uber, Facebook. Эта статья поможет вам лучше их понять и познакомит с основами обхода графа.
Что такое граф? Давайте начнем с краткого определения: граф – это набор вершин или узлов, соединенных ребрами. Граф может быть направленным или неориентированным, он может быть циклическим или ациклическим, он может быть взвешенным или невзвешенным. Граф направлен, если между двумя соединенными узлами есть направление, вы можете сказать, что граф направлен в его визуальном представлении, когда на ребрах есть стрелки. Неориентированные графы не различаются по направлению, например, узел A -> узел B совпадает с узлом B -> узел A в неориентированном графе. Взвешенный граф может представлять через свои ребра произвольные значения, такие как стоимость, расстояние и т. д.
Существует несколько специальных типов графиков: деревья, корневые деревья, DAGS и полные графики.
- Деревья — неориентированный граф без взвешенных ребер. Всегда есть N узлов с N-1 ребрами.
- Корневое дерево — дерево с назначенным узлом дерева, в котором каждое ребро либо направлено от корня, либо направлено к нему. Деревья, где направление уходит от корневого узла, дерево демонстрирует древовидность. Когда направление перемещается к корневому узлу, дерево демонстрирует анти-древовидность.
- DAGS (направленный ациклический граф) — ориентированные графы без циклов. Тип DAG представляет собой двудольный граф. Двудольные графы — это графы, вершины которых можно разделить на две группы U и V так, что каждое ребро соединяет U и V. Это означает, что граф можно раскрасить в два цвета или он не имеет цикла нечетной длины.
- Полный граф — граф, имеющий уникальное ребро между всеми вершинами.
Когда дело доходит до представления графиков, существует несколько способов представления графика. У вас может быть либо список смежности, либо матрица смежности, либо список ребер. В последующих частях статьи я буду реализовывать граф с помощью JavaScript. Вы можете реализовать граф с помощью класса или функции, но в этой статье я буду следовать реализации класса.
Список смежности будет иметь карту с ключами для всех вершин графа. Значения этих ключей представляют собой массив/список других вершин, которые связаны с этим узлом. Вы можете вычислить все ребра графа, перебирая список смежности, а затем перебирая соответствующие массивы. Плюсы использования списка смежности заключаются в том, что он отлично подходит для разреженных графов и эффективен для перебора всех ребер. Недостатки заключаются в том, что он неэффективен по пространству для более плотных графов, медленный поиск ребер и немного более сложное представление, чем его аналоги.
Матрица смежности — это двумерная матрица размерностью N x N. Каждая запись в матрице представляет, существует ли ребро между этими двумя вершинами. Например, matrix[i][j] = true означает, что между вершинами i и j существует ребро, если бы оно было ложным, это означало бы, что ребро не существует. Вместо значений true/false у вас также может быть значение, представляющее вес ребра, если бы это был взвешенный граф. Плюсы матрицы смежности заключаются в том, что она эффективно использует пространство, а поиск ребер является постоянным, это самое простое представление графа. минусы заключаются в том, что матрица занимает n² пространства и времени.
Список ребер обычно представляет собой неупорядоченный список/массив пар вершин или пар + вес. Плюсы заключаются в том, что он отлично подходит для разреженных графов, эффективен итерации и имеет простую структуру. минусы заключаются в том, что он менее эффективен по пространству, а поиск по краям выполняется медленно. Этот метод представления графов не очень распространен, поэтому я покажу только реализации списка смежности и матрицы.
Какие типы задач представлены/решены на графиках?
Графы можно использовать для решения целого ряда задач, изучение графов и их алгоритмов называется теорией графов. Типы задач, решаемых с помощью графов, следующие:
- Кратчайший путь — кратчайшее расстояние между двумя узлами на графике. Карты Google звонят в колокол?
- Связность — существует ли путь от одного узла к другому.
- Сильно связанные компоненты — если группа вершин связана друг с другом. Социальные группы могут быть представлены через сильно связанные компоненты, что такое сплоченная группа друзей, как не набор вершин, которые имеют ребра между собой? 😂
- Задача коммивояжёра. Каков кратчайший путь при наличии списка городов, когда вы посещаете каждый город, начиная с источника и возвращаясь к этому источнику?
- Мостики — ребра при удалении увеличивают количество соединенных компонентов.
- Точки сочленения — удаление вершин увеличивает количество связанных компонентов.
- Минимальное остовное дерево — находит минимальное поддерево, соединяющее все вершины графа.
- Сетевой поток — находит максимальный поток, который вы можете отправить через систему, путем построения графика максимального потока. Начинается с исходного узла и движется к узлу-приемнику.
Большинство перечисленных выше проблем решаются с помощью одного из множества различных графовых алгоритмов. В следующих статьях я расскажу о различных графовых алгоритмах и их реализации на JS. Большинство более сложных алгоритмов графа имеют либо поиск в глубину (DFS), либо поиск в ширину (BFS) в качестве основного режима обхода графа. Ниже я сделаю общий обзор DFS и BFS, а затем перейду к реализации.
Поиск в глубину — это форма обхода графа, в которой используется парадигма «последний пришел — первый ушел» (LIFO). При поиске в глубину вы стремитесь к глубине, обход проходит по уровням дерева/графа, прежде чем вернуться назад. Для этого вы используете стек — будь то явно в итеративном подходе или неявно через стек вызовов в рекурсивном подходе. Вы начинаете со «стартового» узла и добавляете его соседей в стек, после чего вы вытаскиваете из стека другой узел и исследуете его соседей. Если вы когда-либо извлекаете только последний узел, вы проходите через уровни дерева/графа на каждой итерации или вызове этого поиска в глубину.
Поиск в ширину — это форма обхода графа, в которой используется парадигма «первым пришел — первым обслужен» (FIFO). При поиске в ширину вы стремитесь к ширине, обход полностью исследует уровень дерева/графа, прежде чем перейти к следующему уровню. Из-за характера поиска BFS выполняется только итеративно. DFS хорошо подходит для рекурсии из-за природы стека вызовов, однако в BFS единственная работающая структура данных — это очередь, потому что очередь — это FIFO.
Использование DFS или BFS для обхода графа полностью зависит от структуры графа и типа проблемы, которую вы пытаетесь решить. Временная сложность DFS/BFS составляет O(V + E) при использовании списка смежности и O(V²) при использовании матрицы смежности, где V — количество вершин, а E — количество ребер. В списке смежности вы всегда сохраняете информацию только о фактически существующих ребрах, и в худшем случае вы перебираете все вершины и все ребра, чтобы найти целевой узел. В матрице размер матрицы равен V x V, где V — количество вершин. Чтобы найти целевой узел, вы, по сути, проходите через массивы V размером V, что дает вам временную сложность O (V²).
Реализация графа
- Конструктор. Первое, что нужно сделать, это создать класс с именем Graph и инициализировать его списком смежности или матрицей. Список смежности обычно представляет собой либо карту, либо «объект» в JS, а матрица — массив массивов. Если вы используете матрицу, вам нужно будет создать экземпляр графа с количеством узлов, которые вы хотите иметь в графе.
2. Добавить вершину. Второе, что вам нужно настроить, — это способ добавления вершин. Если вы используете матрицу смежности, вам не нужно использовать этот метод, поскольку вершины уже «инициализированы» при создании экземпляра графа. В подходе списка смежности, чтобы добавить вершину, вы просто создаете новый ключ со значением пустого массива.
3. Добавить ребро. Следующим логическим шагом будет добавление соединений между нашими вершинами! Это просто для матриц смежности и несколько сложнее для списков смежности. На первом изображении показан способ добавления ребер в список смежности, а на втором изображен матричный метод. В методе списка смежности я также вызываю метод добавления вершин для вершин, составляющих ребро, в качестве меры предосторожности, чтобы они не существовали изначально. Этот метод addEdge создает ненаправленное ребро, если вы хотите создать направленное ребро, вы должны вставить v2 только в массив v1 или наоборот.
3. Удалить край. Если мы можем добавлять края, мы также должны иметь возможность удалять края! Чтобы удалить ребро в списке смежности, которое представляет ненаправленные ребра, как на изображении ниже, мы должны отфильтровать его из массива ребер соответствующей вершины. В матрице это просто установить для соответствующей записи значение false.
4. Удалить вершину. Мы также должны иметь возможность удалить один узел из нашего графа. Чтобы удалить вершину из списка смежности, нам пришлось бы перебирать ребра этой конкретной вершины и вызывать для них метод removeEdge. Как только это будет сделано, мы удалим ключ вершины из карты/объекта списка смежности. Удаление вершины из матрицы смежности немного отличается и открывает несколько интересных вопросов, которые вы должны задать себе, прежде чем приступить к конкретному методу. Если вы хотите сохранить индексы, с которыми вы ссылаетесь на свои вершины, вы можете потенциально установить массив в матрице [i] равным нулю, чтобы представить вершину как нулевую, а затем перебрать каждую другую строку и установить столбец j равным нулевое значение (matrix[i][j] = null). Если вы не хотите поддерживать исходную нумерацию вершин, вы можете просто отфильтровать строку вершины из матрицы, а затем отфильтровать вершину из оставшихся строк.
ПРИМЕЧАНИЕ. Приведенные ниже методы DFS и BFS будут реализованы только на основе списков смежности. На этом этапе у вас должно быть представление о том, как работают матрицы смежности, и вы должны быть в состоянии изменить приведенные ниже методы, чтобы они соответствовали матрице.
5. Поиск в глубину (рекурсивный). Помните, что я упоминал ранее в статье? Этот подход будет использовать стек вызовов в качестве нашего «стека». Сначала мы инициализируем переменную результатов, которая будет содержать результат нашего поиска в DFS, затем мы инициализируем переменную для отслеживания посещенных узлов. Нам также нужно кэшировать список смежности в отдельную переменную внутри метода, чтобы нам не приходилось беспокоиться о том, кто это, когда наша функция DFS обращается к списку смежности. Функция DFS представляет собой IIFE (немедленно вызываемое функциональное выражение), она вызывается с начальным узлом. Функция сначала проверяет, является ли переданный узел допустимым, если это не так, то возвращается null. Мы помечаем наш узел как посещенный, а затем помещаем его в наш массив результатов. Затем мы перебираем ребра этой вершины и рекурсивно вызываем функцию DFS для соседа, ЕСЛИ он не был посещен. В конце мы можем вернуть наш массив результатов с порядком DFS наших вершин.
6. Поиск в глубину (итеративный). В итеративном подходе мы собираемся явно использовать стек. Подобно рекурсивному подходу, у меня есть массив результатов и посещенная карта/объект. Я инициализирую стек начальным узлом в нем и помечаю его как посещенный. Затем я использую цикл while, чтобы продолжать цикл, пока в стеке есть элементы, на каждой итерации я извлекаю узел и помещаю его в массив результатов. Я перебираю дочерние элементы этого узла, если дочерний элемент не посещается, я посещаю его и добавляю в стек. Я выхожу из цикла, как только стек становится пустым, а затем возвращаю массив результатов.
7. Поиск в ширину. Подход BFS будет почти таким же, как итеративный подход DFS. Вместо использования стека мы собираемся инициализировать очередь переменной start. Для простоты я буду использовать для очереди массив, но на практике для моделирования очереди вам следует использовать структуру данных, такую как связанный список. Переход от обычного массива - это операция O (n), тогда как в связанном списке/очереди это будет O (1). Я также посещаю начальный узел перед переходом в цикл while. Цикл продолжает выполняться, пока в очереди есть элементы. Внутри цикла while узел перемещается из очереди на каждой итерации. Дочерние узлы этого узла изучаются, и если дочерний узел не был посещен, он помечается как посещенный и помещается в очередь. В конце, после завершения цикла, мы возвращаем массив результатов.
Следите за новыми статьями из серии DS & A. В будущем я буду публиковать статьи о расширенных графовых алгоритмах!
Пожалуйста, не стесняйтесь обращаться с вопросами/комментариями!
