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

В этом мы узнаем, как реализовать все эти представления графов в JavaScript, поскольку реализация может меняться в зависимости от языка.

Приступаем к написанию кода

Список смежности

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

В JavaScript нам не нужно создавать чистый связанный список, мы будем использовать встроенные структуры данных Set и Map и обернем все методы внутри JS-класса с именем Graph.

Невзвешенный и неориентированный граф

Итак, сначала мы создали класс с именем Graph, и этот класс имеет только одно свойство с именем adjacencyList. Наш конструктор инициирует свойство с пустой картой. Это означает, что весь наш граф списка смежности будет представлен с использованием карты.

Теперь мы можем добавить некоторые методы внутри класса.

addNode: этот метод добавляет новый узел внутрь графа. Метод получает узел, который мы хотим добавить, и мы используем встроенную функцию set, которая получает два параметра, первый — это ключ, который будет использоваться для получения значения, а второй — значение, которое мы хотим добавить. Здесь значением является новый набор, поскольку во введении мы упомянули, что в списке смежности узел должен быть связан со всеми соседними с ним узлами, чтобы набор содержал все узлы, соседние с узлом, используемым в качестве ключа.

addEdge: ребро — это путь между двумя узлами, так как мы создаем неориентированный граф, это означает, что если есть путь от узла 1 к узлу 2, то есть путь и от узла 2 к узлу 1. Это то, что функция здесь извлекает список соседних узлов для node1 и node2, а затем добавляет обратный узел в каждый список.

getNeighboors: этот метод возвращает все узлы, прилегающие к данному узлу, получая только значение внутри графа, используя данный узел в качестве ключа.

hasEdge: эта функция проверяет, существует ли путь от node1 к node2, для этого она извлекает все узлы, смежные с node1, а затем проверяет, существует ли node2 в этом списке.

Невзвешенный и направленный график

Разница между ориентированным и неориентированным графом заключается в том, что внутри ориентированного графа наличие пути от узла 1 к узлу 2 не означает, что также существует путь от узла 2 к узлу 1, если вы хотите, вам нужно явно создать этот второй путь.

Если мы хотим создать ориентированный граф из предыдущего реализованного кода, нам нужно просто отредактировать метод addEdge, удалив создание второго пути.

Взвешенный график

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

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

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

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

Наконец, узел будет ключом, а вес будет сохраненным значением.

Матрица смежности

Это способ представить график с помощью двумерного массива. Индексы представляют узлы, если значение в ячейке (i,j) равно 1, это означает, что между узлами i и j есть путь, иначе он будет равен 0.

Невзвешенный и неориентированный граф

Мы сохраним общий класс Graph в качестве оболочки.

Поскольку мы создадим двумерный массив, нам нужно заранее знать количество узлов, которые мы хотим сохранить, это роль свойства numberNodes, а затем у нас есть второе, которое представляет сам массив.

Каждый раз, когда создается новый экземпляр графа, мы должны передать количество узлов, а затем мы создаем новый пустой массив, назначенный свойству adjacencyMatrix.

Наконец, мы проходим по этому массиву, назначая каждой ячейке новый массив размером numberNodes, заполненный нулями.

PS: здесь нам не нужен метод для добавления узла внутри Графа.

addEdge: метод получает два узла, а затем мы должны установить значение в ячейке adjacencyMatrix[node1][node2] равным 1, и, поскольку это неориентированный граф, мы должны сделать то же самое для обратного направления adjacencyMatrix[node2][node1].

hasEdge: чтобы проверить, есть ли путь или ребро между двумя заданными узлами, сначала метод проверяет, существуют ли полученные значения в графе, а затем мы проверяем, равно ли значение в adjacencyMatrix[node1][node2] 1, и, поскольку это неориентированный граф, мы также должны проверить обратное направление, если да, мы возвращаем true.

getNeighboors: чтобы получить все узлы, прилегающие к данному узлу, мы возвращаем ячейку в позицию node .

removeEdge: чтобы удалить, мы сначала проверяем, допустимы ли данные значения, если да, мы устанавливаем значение в ячейке (node1, node2) равным 0, и мы должны сделать это для обоих направлений, поскольку это неориентированный график.

Невзвешенный и ориентированный график

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

Взвешенный график

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

Проверьте код ниже:

Вы могли заметить, что в приведенном выше коде, поскольку теперь мы сохраняем расстояние, а не 1, при проверке существования пути мы проверим, отличается ли значение в (node1,node2) от 0.

Заключение

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