ds-kit-js - v1.1.0
    Preparing search index...

    Class Graph<V>

    Граф на списках смежности: ориентированный или неориентированный, взвешенный или нет (вес по умолчанию — 1). Вершинами могут быть любые значения, пригодные как ключи Map.

    const g = new Graph<string>()
      .addEdge('A', 'B', 4)
      .addEdge('A', 'C', 2)
      .addEdge('C', 'B', 1);
    g.shortestPath('A', 'B'); // { distance: 3, path: ['A', 'C', 'B'] }

    Type Parameters

    • V = string
    Index
    constructor
    directed vertexCount edgeCount
    addVertex addEdge removeEdge removeVertex hasVertex hasEdge getWeight neighbors vertices edges bfs dfs shortestPath topologicalSort hasCycle connectedComponents minimumSpanningTree
    • get directed(): boolean

      Returns boolean

    • get vertexCount(): number

      Returns number

    • get edgeCount(): number

      Returns number

    • Parameters

      • v: V

      Returns this

    • Добавляет ребро (и недостающие вершины). Повторный вызов обновляет вес.

      Parameters

      • from: V
      • to: V
      • weight: number = 1

      Returns this

    • Parameters

      • from: V
      • to: V

      Returns boolean

    • Удаляет вершину и все инцидентные ей рёбра.

      Parameters

      • v: V

      Returns boolean

    • Parameters

      • v: V

      Returns boolean

    • Parameters

      • from: V
      • to: V

      Returns boolean

    • Parameters

      • from: V
      • to: V

      Returns number | undefined

    • Все рёбра. В неориентированном графе каждое ребро возвращается один раз.

      Returns Edge<V>[]

    • Обход в ширину; возвращает вершины в порядке посещения.

      Parameters

      • start: V

      Returns V[]

    • Обход в глубину (итеративный, без риска переполнения стека).

      Parameters

      • start: V

      Returns V[]

    • Кратчайший путь алгоритмом Дейкстры, O((V + E) log V).

      Parameters

      • from: V
      • to: V

      Returns ShortestPath<V> | null

      null, если путь не существует.

      RangeError при отрицательном весе ребра.

    • Топологическая сортировка (алгоритм Кана) для ориентированного графа.

      Returns V[]

      Error, если граф неориентированный или содержит цикл.

    • Есть ли в графе цикл.

      Returns boolean

    • Компоненты связности. Для ориентированного графа — компоненты слабой связности (направление рёбер не учитывается).

      Returns V[][]

    • Минимальное остовное дерево (лес) алгоритмом Краскала, O(E log E).

      Returns SpanningTree<V>

      Error для ориентированного графа.

    Settings
    Member Visibility

    On This Page
    Constructors
    Accessors
    Methods