Graph хранит граф списками смежности. Граф может быть ориентированным
или неориентированным, взвешенным или нет (вес ребра по умолчанию — 1).
Вершиной может быть любое значение, пригодное как ключ Map: строки, числа, объекты.
import { Graph } from 'ds-kit-js';
const roads = new Graph<string>() // неориентированный
.addEdge('Москва', 'Тверь', 180)
.addEdge('Тверь', 'Санкт-Петербург', 530)
.addEdge('Москва', 'Владимир', 190)
.addEdge('Владимир', 'Нижний Новгород', 240);
const deps = new Graph<string>({ directed: true }); // ориентированный
| Метод | Описание |
|---|---|
addVertex(v), removeVertex(v) |
добавить или удалить вершину (вместе с её рёбрами) |
addEdge(a, b, w?), removeEdge(a, b) |
добавить или удалить ребро; повторный addEdge обновляет вес |
hasVertex, hasEdge, getWeight |
проверки |
neighbors(v), vertices(), edges() |
списки соседей, вершин и рёбер |
vertexCount, edgeCount |
количество вершин и рёбер |
roads.bfs('Москва'); // в ширину: по удалённости в рёбрах
roads.dfs('Москва'); // в глубину (итеративный, не переполняет стек)
roads.shortestPath('Тверь', 'Нижний Новгород');
// { distance: 610, path: ['Тверь', 'Москва', 'Владимир', 'Нижний Новгород'] }
Возвращает null, если путь не существует. При отрицательном весе ребра
бросает RangeError.
Упорядочивает вершины ориентированного графа так, что каждое ребро ведёт «вперёд». Применяется для порядка сборки, миграций, задач с зависимостями.
const build = new Graph<string>({ directed: true })
.addEdge('utils', 'core')
.addEdge('core', 'app')
.addEdge('ui', 'app');
build.topologicalSort(); // ['utils', 'ui', 'core', 'app']
build.hasCycle(); // false
Если в графе есть цикл, метод бросает Error.
new Graph<number>().addEdge(1, 2).addEdge(3, 4).addVertex(5).connectedComponents();
// [[1, 2], [3, 4], [5]]
Для ориентированного графа метод возвращает компоненты слабой связности: направление рёбер не учитывается.
Находит набор рёбер минимального суммарного веса, связывающий все вершины. Если граф несвязный, результатом будет остовный лес.
const { weight, edges } = roads.minimumSpanningTree();
Работает только для неориентированных графов.