В предыдущих статьях я исследовал различные структуры данных — от связанных списков и деревьев до хеш-таблиц. В этой статье я рассмотрю основы работы со структурой данных графа.
Для начала давайте определим структуру данных графа. Графики представляют собой наборы точек данных, называемых узлами или вершинами, которые соединяются друг с другом. То, как каждый узел соединяется с другим, определяет значение данных графика, что делает графики отличными для отображения того, как один элемент связан с другим.
Изображение ниже является примером базового графика.
Графики используются для моделирования данных по всему Интернету. От кругов друзей на Facebook до рекомендаций продуктов, которые другие люди приобрели на Amazon, графики данных делают это возможным.
Графы могут быть двух основных видов — ориентированные или неориентированные графы и взвешенные/невзвешенные графы. Эти две категории не являются взаимоисключающими, поэтому, например, можно одновременно иметь ориентированный и взвешенный граф.
Неориентированный граф
Неориентированный граф — это когда каждый узел имеет взаимную связь. Итак, вы можете сказать, что A подключен к B, а B подключен к A. Реальный пример этого — когда вы добавляете друга на Facebook. Каждый пользователь теперь имеет полный доступ к общедоступному контенту другого пользователя.
Направленный граф
В ориентированном графе связи между двумя узлами не обязательно взаимны. Таким образом, A может соединиться с B, но B не соединяется автоматически с A. Примером ориентированного графа из реального мира являются подписчики в Instagram. Когда вы подписываетесь на новую учетную запись, эта новая учетная запись не подписывает вас автоматически.
Это представлено на графике ниже, где некоторые стрелки являются двунаправленными, а другие — однонаправленными.
Взвешенный и невзвешенный график
Взвешенные графики добавляют дополнительную информацию к отношениям между двумя узлами. Это делается путем присвоения числового значения ребру — линии, соединяющей два узла. Это значение может представлять расстояние или насколько сильно связаны два узла. Реальный пример взвешенного графа — Google Maps.
Когда вы ищете направления для местоположения, Карты Google определяют самый быстрый маршрут, который обычно определяется путем нахождения кратчайшего расстояния между начальным и конечным узлами.
Как создать график
Графические данные могут быть представлены в двух основных форматах:
- Список смежности
- Матрица смежности
Оба достигают одной и той же цели, однако каждый из них имеет свои плюсы и минусы. Список смежности часто создается с помощью хеш-таблицы. Ключ — это узел, а значения — все его соединения.
В матрице смежности данные часто хранятся во вложенных массивах. Самый простой способ изобразить матрицу смежности — представить себе электронную таблицу. В неориентированном графе каждый узел представляет столбец и строку. Каждая ячейка между строкой и столбцом показывает, соединен ли узел с другим. Ноль обычно означает отсутствие связи, а единица означает наличие связи.
Разница в их конструкции приводит к различиям в производительности в зависимости от желаемой операции. В общем, если в ваших данных много вершин (узлов), но каждая вершина имеет ограниченное количество соединений, лучше использовать список смежности. Если у вас много вершин, и каждая из них связана со многими другими вершинами, то лучше использовать матрицу смежности.
Добавление и удаление данных
Добавить данные на график довольно просто. Предполагая, что мы используем список смежности, мы просто создаем новый ключ в нашей хеш-таблице. Затем мы можем создать еще один метод для обработки добавления соединений (называемых ребрами). То, как устанавливаются эти связи, будет зависеть от того, создаем ли мы ориентированный или неориентированный граф.
При удалении ребра (соединения) мы перебираем пары ключ-значение и удаляем нужное ребро. При удалении всей вершины мы выполняем тот же процесс, что и при удалении ребра, за исключением того, что в конце мы также удаляем ключ из нашей хэш-таблицы.
Следующий код представляет собой базовый скелет для реализации неориентированного графа с использованием списка смежности.
class Graph {
constructor(){
this.list = {}
}
addVertex(key){
if (!this.list[key]) this.list[key] = []
}
addEdge(v1, v2){
if (this.list[v1]) this.list[v1].push(v2)
if (this.list[v2]) this.list[v2].push(v1)
}
removeEdge(v1, v2){
if (this.list[v1]) {
this.list[v1] = this.list[v1].filter(value => value !== v2)
}
if (this.list[v2]){
this.list[v2] = this.list[v2].filter(value => value !== v1)
}
}
removeVertex(v1){
if (this.list[v1]){
this.list[v1].forEach((v2) => {
this.removeEdge(v1, v2)
})
}
delete this.list[v1]
}
}
Обход графа
Как и при обходе бинарного дерева, существует два основных варианта обхода графа — поиск в ширину и поиск в глубину. При поиске в ширину мы сначала посещаем все соединения данной вершины, прежде чем перейти к следующей вершине в графе. При поиске в глубину мы следуем заданному соединению до тех пор, пока оно не зайдет в тупик, а затем возвращаемся назад, чтобы следовать другому соединению в вершине.
Важно понимать, что при обходе графа не обязательно есть один правильный ответ. Есть много путей, по которым можно коснуться каждой вершины графа. Кроме того, не существует единственно правильной отправной точки. Наши обходы должны начинаться с того, что нам говорят, какой узел смотреть в первую очередь. Это отличается от деревьев, где есть корневой узел, который запускает поиск.
Ключевой концепцией, которую необходимо понимать при обходе графа, является отслеживание вершин, которые вы уже посетили. При любом обходе графа вы неизбежно встретите вершину, которую уже видели ранее. Вам нужен способ отслеживать эти увиденные вершины, чтобы ваш обход не длился вечно.
На изображении ниже показан график, на котором видны вершины A B D. С правой стороны настроена хеш-таблица для их отслеживания.
Реализация кода в глубину и в ширину
- Получив узел, добавьте его в стек или очередь, создайте цикл, который выполняется до тех пор, пока в стеке или очереди есть узлы.
- Вытолкните или сдвиньте узел. Если вы НЕ уже посетили этот узел, перейдите к нему. Добавьте его в свой массив результатов. Добавьте его в хеш-таблицу посещенных узлов.
- Прокрутите все соединения, которые есть у этого узла, и добавьте их в свой стек или очередь.
- Когда стек или очередь заканчиваются, верните массив результатов.
DFS_iterative(vertex){
let visited = {}
let results = []
let stack = []
stack.push(vertex)
while (stack.length > 0) {
vertex = stack.pop();
if (!visited[vertex]) {
results.push(vertex)
visited[vertex] = true
this.list[vertex].forEach(v => {
stack.push(v)
})
}
}
return results
}
BFS_iterative(vertex){
let visited = {}
let results = []
let queue = []
queue.push(vertex)
while (queue.length > 0){
vertex = queue.shift();
if (!visited[vertex]){
visited[vertex] = true;
results.push(vertex)
this.list[vertex].forEach(v => {
queue.push(v)
})
}
}
return results;
}
