Граф
Описание
Граф (graph) - это абстрактный тип данных, реализующий математические концепции направленного и ненаправленного (ориентированного и неориентированного) графов (соответствующий раздел математики называется теорией графов).
Граф состоит из конечного (потенциально изменяющегося) набора узлов (вершин, точек) (nodes, vertices, points), а также набора ненаправленных или, соответственно, направленных пар этих узлов. Эти пары называются ребрами (арки, линии, стрелки - для направленного графа) (edges, arcs, lines, arrows). Узлы могут быть как частью графа, так и внешними сущностями, представленными целочисленными индексами или ссылками.
Для разных областей применения графы могут различаться направленностью, ограничениями на количество ребер и дополнительными данными о вершинах и ребрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены в виде графов. Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершинами будут выступать статьи, а ребрами - гиперссылки.
Примеры неориентированного и ориентированного графов
Обратите внимание: ребра графа часто имеют вес, который используется для определения "стоимости" пути.
Любопытная визуализация графа.
Реализация
Начнем с реализации узла графа. Для представления ребер узла целесообразно использовать связный список (см. часть 1, раздел 1):
// data-structures/graph/node.js
// Связный список
import LinkedList from '../linked-list'
// Функция сравнения ребер
const edgeComparator = (a, b) => {
if (a.getKey() === b.getKey()) {
return 0
}
return a.getKey() < b.getKey() ? -1 : 1
}
export default class Node {
constructor(value) {
if (!value) {
throw new Error('Узел графа должен иметь значение!')
}
// Значение узла
this.value = value
// Связный список ребер
this.edges = new LinkedList(edgeComparator)
}
}
Методы добавления и удаления ребер:
// Добавляет ребро в список
addEdge(edge) {
this.edges.append(edge)
return this
}
// Удаляет ребро из списка
removeEdge(edge) {
this.edges.remove(edge)
return this
}
// Удаляет все ребра
removeAllEdges() {
this.getEdges().forEach((edge) => {
this.removeEdge(edge)
})
return this
}
Методы получения соседних узлов, ребер, длины и значения узла:
// Возвращает список соседних узлов
getNeighbors() {
const edges = this.edges.toArray()
return edges.map((node) =>
node.value.from === this ? node.value.to : node.value.from,
)
}
// Возвращает список ребер в виде массива значений
getEdges() {
return this.edges.toArray().map((node) => node.value)
}
// Возвращает длину (глубину) узла
getDegree() {
return this.edges.toArray().length
}
// Возвращает значение узла
getKey() {
return this.value
}
Методы определения наличия ребер и соседей:
// Определяет наличие ребра
hasEdge(edge) {
const _edge = this.edges.find({ cb: (node) => node === edge })
return Boolean(_edge)
}
// Определяет наличие соседа
hasNeighbor(node) {
const _node = this.edges.find({
cb: (n) => n.to === node || n.from === node,
})
return Boolean(_node)
}
Метод поиска ребра по узлу:
// Выполняет поиск ребра по узлу
findEdge(node) {
const _node = this.edges.find({
cb: (n) => n.to === node || n.from === node,
})
return _node ? _node.value : null
}
Наконец, вспомогательный метод стрингификации узла:
// Возвращает строковое представление узла.
// Принимает кастомную функцию стрингификации
toString(cb) {
return cb ? cb(this.value) : `${this.value}`
}
Полный код узла графа
Код ребра графа до неприличия прост, поэтому привожу его целиком:
// data-structures/graph/edge.js
export default class Edge {
constructor(from, to, weight = 0) {
// Начальный узел
this.from = from
// Конечный узел
this.to = to
// Вес ребра
this.weight = weight
}
// Возвращает ключ ребра
getKey() {
const fromKey = this.from.getKey()
const toKey = this.to.getKey()
// Например, `A_B`
return `${fromKey}_${toKey}`
}
// Инвертирует ребро
reverse() {
const tmp = this.from
this.from = this.to
this.to = tmp
return this
}
// Преобразует ребро в строку
toString() {
return this.getKey()
}
}
Тесты для узла
Запускаем тесты:
npm run test ./data-structures/graph/__tests__/node
Тесты для ребра
Запускаем тесты:
npm run test ./data-structures/graph/__tests__/edge
Приступаем к реализации графа:
// data-structures/graph/index.js
export default class Graph {
constructor(isDirected = false) {
// Индикатор направленности графа
// (по умолчанию граф является ненаправленным)
this.isDirected = isDirected
// Узлы
this.nodes = {}
// Ребра
this.edges = {}
}
}
Метод добавления узла в граф и несколько "геттеров":
// Добавляет узел в граф
addNode(newNode) {
this.nodes[newNode.getKey()] = newNode
return this
}
// Возвращает узел по ключу
getNodeByKey(key) {
return this.nodes[key]
}
// Возвращает соседние узлы
getNeighbors(node) {
return node.getNeighbors()
}
// Возвращает значения всех узлов
getAllNodes() {
return Object.values(this.nodes)
}
// Возвращает значения всех ребер
getAllEdges() {
return Object.values(this.edges)
}
Методы добавления, удаления и поиска ребер:
// Добавляет ребро в граф
addEdge(newEdge) {
// Пытаемся найти начальную и конечную вершины
let from = this.getNodeByKey(newEdge.from.getKey())
let to = this.getNodeByKey(newEdge.to.getKey())
// Добавляем начальную вершину
if (!from) {
this.addNode(newEdge.from)
from = this.getNodeByKey(newEdge.from.getKey())
}
// Добавляем конечную вершину
if (!to) {
this.addNode(newEdge.to)
to = this.getNodeByKey(newEdge.to.getKey())
}
// Если ребро уже добавлено
if (this.edges[newEdge.getKey()]) {
throw new Error('Ребро уже добавлено!')
} else {
// Добавляем ребро
this.edges[newEdge.getKey()] = newEdge
}
// Добавляем ребро в вершины
if (this.isDirected) {
from.addEdge(newEdge)
} else {
from.addEdge(newEdge)
to.addEdge(newEdge)
}
return this
}
// Удаляет ребро из графа
removeEdge(edge) {
if (this.edges[edge.getKey()]) {
// Удаляем ребро
delete this.edges[edge.getKey()]
} else {
throw new Error('Ребро не найдено!')
}
// Пытаемся найти начальную и конечную вершины
let from = this.getNodeByKey(edge.from.getKey())
let to = this.getNodeByKey(edge.to.getKey())
// Удаляем ребро из вершин
from && from.removeEdge(edge)
to && to.removeEdge(edge)
}
// Находит ребро в графе
findEdge(from, to) {
// Находим узел по начальному ключу
const node = this.getNodeByKey(from.getKey())
if (!node) return null
// Пытаемся найти конечное ребро
return node.findEdge(to)
}
Методы получения веса графа, инвертирования графа и получения индексов узлов:
// Возвращает вес графа
getWeight() {
// Суммируем веса всех ребер
return this.getAllEdges().reduce((acc, edge) => acc + edge.weight, 0)
}
// Инвертирует граф
reverse() {
// Для каждого ребра
this.getAllEdges().forEach((edge) => {
// Удаляем ребро из графа
this.removeEdge(edge)
// Инвертируем ребро
edge.reverse()
// Снова добавляем ребро в граф
this.addEdge(edge)
})
return this
}
// Возвращает индексы узлов в виде объекта
getNodesIndices() {
const indices = {}
this.getAllNodes().forEach((node, index) => {
indices[node.getKey()] = index
})
return indices
}
Метод получения матрицы смежности:
// Возвращает матрицу смежности
getAdjacencyMatrix() {
// Узлы
const nodes = this.getAllNodes()
// Индексы узлов
const indices = this.getNodesIndices()
// Инициализируем матрицу смежности (заполняем ее `null`)
const matrix = new Array(nodes.length)
.fill()
.map(() => new Array(nodes.length).fill(null))
// Формируем матрицу.
// Перебираем узлы
nodes.forEach((node, index) => {
// Перебираем соседей узла
node.getNeighbors().forEach((neighbor) => {
// Индекс соседа
const neighborIndex = indices[neighbor.getKey()]
// [индекс узла][индекс соседа] = вес ребра
matrix[index][neighborIndex] = this.findEdge(node, neighbor).weight
})
})
return matrix
}
Наконец, вспомогательный метод преобразования графа в строку:
// Возвращает строковое представление графа
toString() {
return Object.keys(this.nodes).toString()
}
Полный код графа
Тесты
Запускаем тесты:
npm run test ./data-structures/graph/__tests__/graph
