JavaScript: структуры данных и алгоритмы. Часть 4

Привет, друзья!

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

• Первая часть
• Вторая часть
• Третья часть
• Пятая часть

Сегодня мы рассмотрим дерево отрезков, дерево Фенвика, а также граф (направленный и ненаправленный).

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

Интересно? Тогда прошу под кат.

12. Дерево отрезков

Описание

• Википедия
• YouTube

Дерево отрезков (сегментов) (segment tree), также известное как статистическое дерево (statistic tree) — это структура данных, которая используется для хранения информации об отрезках (сегментах, диапазонах). Эта структура данных позволяет запрашивать, какой сегмент содержит определенное значение. По сути, дерево отрезков является статичной структурой данных — ее структура не может меняться после создания.

Дерево отрезков — это двоичное дерево (binary tree, см. часть 3, раздел 9). Корень дерева представляет весь массив. Потомки дерева представляют левую и правую половины массива. Аналогично, потомки каждого узла представляют половины массива, соответствующего узлу.

Дерево строится снизу вверх. Значение предка — это значение минимального потомка (или другое значение в зависимости от переданной функции). Построение дерева занимает время O(n log n). Количество операций — это высота дерева и равняется O(n log n). Для выполнения запросов диапазона (range queries) каждый узел разбивает запрос на две части, по одному подзапросу для каждого потомка. Если запрос содержит весь подмассив узла, мы можем вернуть предварительно вычисленное значение узла. Эта оптимизация позволяет добиться O(n log n) операций.

Случаи применения

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

Такие деревья часто применяются в вычислительной геометрии и географических информационных системах.

Наша реализация дерева отрезков будет принимать любую функцию (принимающую два параметра), позволяя выполнять разные запросы диапазона.

Интерактивную визуализацию дерева отрезков можно посмотреть здесь.

Сложность

Временная

Поиск	Запрос диапазона
O(log(n))	O(log(n))

Пространственная

O(n)

Реализация

Начнем с реализации вспомогательной функции определения того, является ли переданное число результатом возведения числа 2 в какую-либо степень:

// algorithms/math/is-power-of-two.js
export default function isPowerOfTwo(n) {
  // 1 (2^0) - это наименьший результат возведения числа 2 в какую-либо степень
  if (n < 1) return false

  // Выясняем, можем ли мы разделить переданное число на 2 без остатка
  let _n = n
  while (_n !== 1) {
    // Ненулевой остаток свидетельствует о том,
    // что переданное число не может быть результатом возведения числа 2
    // в какую - либо степень
    if (_n % 2 !== 0) return false
    _n /= 2
  }

  return true
}

Напишем тест для этой функции:

// algorithms/math/__tests__/is-power-of-two.test.js
import isPowerOfTwo from '../is-power-of-two'

describe('isPowerOfTwo', () => {
  it('должен проверить, является ли переданное число результатом возведения числа 2 в какую-либо степень', () => {
    expect(isPowerOfTwo(-1)).toBe(false)
    expect(isPowerOfTwo(0)).toBe(false)
    expect(isPowerOfTwo(1)).toBe(true)
    expect(isPowerOfTwo(2)).toBe(true)
    expect(isPowerOfTwo(3)).toBe(false)
    expect(isPowerOfTwo(4)).toBe(true)
    expect(isPowerOfTwo(5)).toBe(false)
    expect(isPowerOfTwo(6)).toBe(false)
    expect(isPowerOfTwo(7)).toBe(false)
    expect(isPowerOfTwo(8)).toBe(true)
    expect(isPowerOfTwo(10)).toBe(false)
    expect(isPowerOfTwo(12)).toBe(false)
    expect(isPowerOfTwo(16)).toBe(true)
    expect(isPowerOfTwo(31)).toBe(false)
    expect(isPowerOfTwo(64)).toBe(true)
    expect(isPowerOfTwo(1024)).toBe(true)
    expect(isPowerOfTwo(1023)).toBe(false)
  })
})

Запускаем этот тест:

npm run test ./algorithms/math/__tests__/is-power-of-two

Результат:

Приступаем к реализации дерева:

// data-structures/tree/segment-tree.js
// Функция определения того, является ли переданное число
// результатом возведения числа 2 в какую-либо степень
// (далее - степенью 2)
import isPowerOfTwo from '../../algorithms/math/is-power-of-two'

export default class SegmentTree {
  constructor(arr, fn, fb) {
    this.arr = arr
    // Основная операция
    this.fn = fn
    // Резервная операция
    this.fb = fb
    // Инициализируем представление дерева в виде массива
    this.tree = this.initTree(arr)
    // Строим дерево
    this.buildTree()
  }
}

Метод инициализации дерева в виде массива:

// Инициализирует представление дерева в виде массива
initTree(arr) {
  let treeLength
  const arrLength = arr.length

  if (isPowerOfTwo(arrLength)) {
    // Если длина массива является степенью 2
    treeLength = arrLength * 2 - 1
  } else {
    // Если длина массива не является степенью 2,
    // нужно найти следующее число, которое является таковым,
    // и использовать его для вычисления длины дерева.
    // Это обусловлено тем, что пустые потомки идеального
    // бинарного дерева должны быть заполнены `null`
    const currentPower = Math.floor(Math.log2(arrLength))
    const nextPower = currentPower + 1
    const nextPowerOfTwoN = 2 ** nextPower

    treeLength = nextPowerOfTwoN * 2 - 1
  }

  return new Array(treeLength).fill(null)
}

Метод построения дерева:

// Строит дерево
buildTree() {
  const leftIndex = 0
  const rightIndex = this.arr.length - 1
  const position = 0
  // Обращаемся к рекурсии
  this.buildTreeRecursively(leftIndex, rightIndex, position)
}

// Строит дерево рекурсивно
buildTreeRecursively(leftIndex, rightIndex, position) {
  // Если левый и правый индексы совпадают, значит,
  // мы закончили деление пополам и добрались до листового узла.
  // Значение листа нужно копировать из массива в дерево
  if (leftIndex === rightIndex) {
    this.tree[position] = this.arr[leftIndex]
    return
  }

  // Делим массив на две равные части и обрабатываем каждую рекурсивно
  const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
  // Обрабатываем левую половину
  this.buildTreeRecursively(
    leftIndex,
    middleIndex,
    this.getLeftChildIndex(position),
  )
  // Обрабатываем правую половину
  this.buildTreeRecursively(
    middleIndex + 1,
    rightIndex,
    this.getRightChildIndex(position),
  )

  // После заполнения всех листьев,
  // мы можем построить дерево снизу вверх
  // с помощью переданной функции
  this.tree[position] = this.fn(
    this.tree[this.getLeftChildIndex(position)],
    this.tree[this.getRightChildIndex(position)],
  )
}

Метод выполнения запроса диапазона:

// Выполняет запрос диапазона
rangeQuery(queryLeftIndex, queryRightIndex) {
  const leftIndex = 0
  const rightIndex = this.arr.length - 1
  const position = 0
  // Обращаемся к рекурсии
  return this.rangeQueryRecursively(
    queryLeftIndex,
    queryRightIndex,
    leftIndex,
    rightIndex,
    position,
  )
}

// Выполняет запрос диапазона рекурсивно
rangeQueryRecursively(
  queryLeftIndex,
  queryRightIndex,
  leftIndex,
  rightIndex,
  position,
) {
  if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
    // Полное перекрытие
    return this.tree[position]
  }

  if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
    // Перекрытие отсутствует
    return this.fb
  }

  // Частичное перекрытие
  const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
  const leftFnResult = this.rangeQueryRecursively(
    queryLeftIndex,
    queryRightIndex,
    leftIndex,
    middleIndex,
    this.getLeftChildIndex(position),
  )
  const rightFnResult = this.rangeQueryRecursively(
    queryLeftIndex,
    queryRightIndex,
    middleIndex + 1,
    rightIndex,
    this.getRightChildIndex(position),
  )

  // Обрабатываем узлы с помощью переданной функции
  // и возвращаем результат
  return this.fn(leftFnResult, rightFnResult)
}

Вспомогательные методы получения индексов потомков:

// Возвращает индекс левого потомка
getLeftChildIndex(parentIndex) {
  return parentIndex * 2 + 1
}

// Возвращает индекс правого потомка
getRightChildIndex(parentIndex) {
  return parentIndex * 2 + 2
}

Полный код дерева отрезков:

// Функция определения того, является ли переданное число
// результатом возведения числа 2 в какую-либо степень
// (далее - степенью 2)
import isPowerOfTwo from '../../algorithms/math/is-power-of-two'

export default class SegmentTree {
  constructor(arr, fn, fb) {
    this.arr = arr
    // Основная операция
    this.fn = fn
    // Резервная операция
    this.fb = fb
    // Инициализируем представление дерева в виде массива
    this.tree = this.initTree(arr)
    // Строим дерево
    this.buildTree()
  }

  // Инициализирует представление дерева в виде массива
  initTree(arr) {
    let treeLength
    const arrLength = arr.length

    if (isPowerOfTwo(arrLength)) {
      // Если длина массива является степенью 2
      treeLength = arrLength * 2 - 1
    } else {
      // Если длина массива не является степенью 2,
      // нужно найти следующее число, которое является таковым,
      // и использовать его для вычисления длины дерева.
      // Это обусловлено тем, что пустые потомки идеального
      // бинарного дерева должны быть заполнены `null`
      const currentPower = Math.floor(Math.log2(arrLength))
      const nextPower = currentPower + 1
      const nextPowerOfTwoN = 2 ** nextPower

      treeLength = nextPowerOfTwoN * 2 - 1
    }

    return new Array(treeLength).fill(null)
  }

  // Строит дерево
  buildTree() {
    const leftIndex = 0
    const rightIndex = this.arr.length - 1
    const position = 0
    // Обращаемся к рекурсии
    this.buildTreeRecursively(leftIndex, rightIndex, position)
  }

  // Строит дерево рекурсивно
  buildTreeRecursively(leftIndex, rightIndex, position) {
    // Если левый и правый индексы совпадают, значит,
    // мы закончили деление пополам и добрались до листового узла.
    // Значение листа нужно копировать из массива в дерево
    if (leftIndex === rightIndex) {
      this.tree[position] = this.arr[leftIndex]
      return
    }

    // Делим массив на две равные части и обрабатываем каждую рекурсивно
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
    // Обрабатываем левую половину
    this.buildTreeRecursively(
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    )
    // Обрабатываем правую половину
    this.buildTreeRecursively(
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    )

    // После заполнения всех листьев,
    // мы можем построить дерево снизу вверх
    // с помощью переданной функции
    this.tree[position] = this.fn(
      this.tree[this.getLeftChildIndex(position)],
      this.tree[this.getRightChildIndex(position)],
    )
  }

  // Выполняет запрос диапазона
  rangeQuery(queryLeftIndex, queryRightIndex) {
    const leftIndex = 0
    const rightIndex = this.arr.length - 1
    const position = 0
    // Обращаемся к рекурсии
    return this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      rightIndex,
      position,
    )
  }

  // Выполняет запрос диапазона рекурсивно
  rangeQueryRecursively(
    queryLeftIndex,
    queryRightIndex,
    leftIndex,
    rightIndex,
    position,
  ) {
    if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
      // Полное перекрытие
      return this.tree[position]
    }

    if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
      // Перекрытие отсутствует
      return this.fb
    }

    // Частичное перекрытие
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
    const leftFnResult = this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    )
    const rightFnResult = this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    )

    // Обрабатываем узлы с помощью переданной функции
    // и возвращаем результат
    return this.fn(leftFnResult, rightFnResult)
  }

  // Возвращает индекс левого потомка
  getLeftChildIndex(parentIndex) {
    return parentIndex * 2 + 1
  }

  // Возвращает индекс правого потомка
  getRightChildIndex(parentIndex) {
    return parentIndex * 2 + 2
  }
}

Тестирование

Проверяем, что наш код работает, как ожидается:

// data-structures/tree/__tests__/segment-tree.test.js
import SegmentTree from '../segment-tree'

describe('SegmentTree', () => {
  it('должен построить дерево для массива #0 с длиной, являющейся степенью 2', () => {
    const array = [-1, 2]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([-1, -1, 2])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить дерево для массива #1 с длиной, являющейся степень 2', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([-1, -1, 0, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить дерево для массива #0 с длиной, НЕ являющейся степень 2', () => {
    const array = [0, 1, 2]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([0, 0, 2, 0, 1, null, null])
    expect(segmentTree.tree.length).toBe(2 * 4 - 1)
  })

  it('должен построить дерево для массива #1 с длиной, НЕ являющейся степень 2', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([
      -1,
      -1,
      0,
      -1,
      4,
      0,
      1,
      -1,
      3,
      null,
      null,
      0,
      2,
      null,
      null,
    ])
    expect(segmentTree.tree.length).toBe(2 * 8 - 1)
  })

  it('должен построить максимальное дерево (предок является максимальным потомком)', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.max, -Infinity)

    expect(segmentTree.tree).toEqual([4, 2, 4, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить суммарное дерево (редок является суммой потомков)', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, (a, b) => a + b, 0)

    expect(segmentTree.tree).toEqual([5, 1, 4, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен выполнить минимальный запрос диапазона на массиве с длиной, являющейся степенью 2', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.rangeQuery(0, 5)).toBe(-1)
    expect(segmentTree.rangeQuery(0, 2)).toBe(-1)
    expect(segmentTree.rangeQuery(1, 3)).toBe(0)
    expect(segmentTree.rangeQuery(2, 4)).toBe(0)
    expect(segmentTree.rangeQuery(4, 5)).toBe(1)
    expect(segmentTree.rangeQuery(2, 2)).toBe(4)
  })

  it('должен выполнить минимальный запрос диапазона на массиве с длиной, НЕ являющейся степенью 2', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.rangeQuery(0, 4)).toBe(-1)
    expect(segmentTree.rangeQuery(0, 1)).toBe(-1)
    expect(segmentTree.rangeQuery(1, 3)).toBe(0)
    expect(segmentTree.rangeQuery(1, 2)).toBe(2)
    expect(segmentTree.rangeQuery(2, 3)).toBe(0)
    expect(segmentTree.rangeQuery(2, 2)).toBe(4)
  })

  it('должен выполнить максимальный запрос диапазона', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.max, -Infinity)

    expect(segmentTree.rangeQuery(0, 5)).toBe(4)
    expect(segmentTree.rangeQuery(0, 1)).toBe(3)
    expect(segmentTree.rangeQuery(1, 3)).toBe(4)
    expect(segmentTree.rangeQuery(2, 4)).toBe(4)
    expect(segmentTree.rangeQuery(4, 5)).toBe(2)
    expect(segmentTree.rangeQuery(3, 3)).toBe(0)
  })

  it('должен выполнить суммарный запрос диапазона', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, (a, b) => a + b, 0)

    expect(segmentTree.rangeQuery(0, 5)).toBe(9)
    expect(segmentTree.rangeQuery(0, 1)).toBe(2)
    expect(segmentTree.rangeQuery(1, 3)).toBe(7)
    expect(segmentTree.rangeQuery(2, 4)).toBe(6)
    expect(segmentTree.rangeQuery(4, 5)).toBe(3)
    expect(segmentTree.rangeQuery(3, 3)).toBe(0)
  })
})

Запускаем тесты:

npm run test ./data-structures/tree/__tests__/segment-tree

Результат:

13. Дерево Фенвика

Описание

• Википедия
• YouTube

Дерево Фенвика (Fenwick tree) или двоичное индексированное дерево (ДИД, binary indexed tree, BIT) — это структура данных, которая позволяет эффективно обновлять элементы и вычислять их суммы.

По сравнению с обычным массивом, ДИД позволяет достичь лучшего баланса между двумя операциями: обновлением элементов и вычислением суммы элементов. В массиве n чисел можно хранить либо сами числа, либо их суммы. В первом случае вычисление суммы чисел занимает линейное время. Во втором случае обновление элемента занимает линейное время. Противоположные операции выполняются за константное время. ДИД позволяет выполнять обе операции за время O(log n). Это достигается за счет представления чисел в виде дерева, где значением каждого узла является сумма чисел поддерева. Структура дерева позволяет выполнять операции за O(log n) доступов к узлам.

Особенности реализации

ДИД представлено в виде массива. Каждый узел дерева хранит сумму узлов некоторого поддерева. Размер ДИД равен n, где n — размер исходного массива. В нашей реализации будет использоваться размер n+1 для простоты. Индексация начинается с 1.

Пример получения суммы элементов с помощью ДИД

• каждый узел имеет индекс (синий) и значение по индексу (зеленый)
• при запросе суммы i, возвращается сумма BITree[i] и всех предков i
• индекс предка i может быть получен с помощью следующей формулы: parent(i) = i - i & (-i). Данная операция удаляет последний установленный бит i. Например, если i=12, то parent(i) вернет 8

Анимированный пример создания ДИД для массива [1, 2, 3, 4, 5] путем добавления элементов одного за другим:

Интерактивную визуализацию ДИД можно посмотреть здесь.

Сложность

Временная

Запрос суммы	Обновление
O(log(n))	O(log(n))

Пространственная

O(n)

Реализация

Приступаем к реализации дерева Фенвика:

// data-structures/tree/fenwick-tree.js
export default class FenwickTree {
  // Конструктор создает дерево Фенвика размера `size`,
  // однако, размер дерева `n+1`, потому что индексация начинается с `1`
  constructor(size) {
    this.size = size
    // Заполняем массив нулями
    this.tree = new Array(size + 1).fill(0)
  }
}

Метод добавления значения к существующему на определенной позиции:

// Прибавляет значение к существующему на указанной позиции
increase(position, value) {
  if (position < 1 || position > this.size) {
    throw new Error('Позиция находится за пределами разрешенного диапазона')
  }

  // magic! :D
  for (let i = position; i <= this.size; i += i & -i) {
    this.tree[i] += value
  }

  return this
}

Метод получения суммы от индекса 1 до определенной позиции:

// Возвращает сумму от индекса 1 до указанной позиции
query(position) {
  if (position < 1 || position > this.size) {
    throw new Error('Позиция находится за пределами разрешенного диапазона')
  }

  let sum = 0

  // magic! :D
  for (let i = position; i > 0; i -= i & -i) {
    sum += this.tree[i]
  }

  return sum
}

Метод получения суммы между двумя индексами:

// Возвращает сумму от `leftIndex` до `rightIndex`
queryRange(leftIndex, rightIndex) {
  if (leftIndex > rightIndex) {
    throw new Error('Левый индекс не может превышать правый')
  }

  if (leftIndex === 1) {
    return this.query(rightIndex)
  }

  return this.query(rightIndex) - this.query(leftIndex - 1)
}

Полный код дерева Фенвика:

export default class FenwickTree {
  // Конструктор создает дерево Фенвика размера `size`,
  // однако, размер дерева `n+1`, потому что индексация начинается с `1`
  constructor(size) {
    this.size = size
    // Заполняем массив нулями
    this.tree = new Array(size + 1).fill(0)
  }

  // Прибавляет значение к существующему на указанной позиции
  increase(position, value) {
    if (position < 1 || position > this.size) {
      throw new Error('Позиция находится за пределами разрешенного диапазона')
    }

    // magic! :D
    for (let i = position; i <= this.size; i += i & -i) {
      this.tree[i] += value
    }

    return this
  }

  // Возвращает сумму от индекса 1 до указанной позиции
  query(position) {
    if (position < 1 || position > this.size) {
      throw new Error('Позиция находится за пределами разрешенного диапазона')
    }

    let sum = 0

    // magic! :D
    for (let i = position; i > 0; i -= i & -i) {
      sum += this.tree[i]
    }

    return sum
  }

  // Возвращает сумму от `leftIndex` до `rightIndex`
  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      throw new Error('Левый индекс не может превышать правый')
    }

    if (leftIndex === 1) {
      return this.query(rightIndex)
    }

    return this.query(rightIndex) - this.query(leftIndex - 1)
  }
}

Тестирование

Проверяем, что наш код работает, как ожидается:

// data-structures/tree/__tests__/fenwick-tree.test.js
import FenwickTree from '../fenwick-tree'

describe('FenwickTree', () => {
  it('должен создать деревья правильного размера', () => {
    const tree1 = new FenwickTree(5)
    expect(tree1.tree.length).toBe(5 + 1)

    for (let i = 0; i < 5; i += 1) {
      expect(tree1.tree[i]).toBe(0)
    }

    const tree2 = new FenwickTree(50)
    expect(tree2.tree.length).toBe(50 + 1)
  })

  it('должен создать правильное дерево', () => {
    const inputArray = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]

    const tree = new FenwickTree(inputArray.length)
    expect(tree.tree.length).toBe(inputArray.length + 1)

    inputArray.forEach((value, index) => {
      tree.increase(index + 1, value)
    })

    expect(tree.tree).toEqual([0, 3, 5, -1, 10, 5, 9, -3, 19, 7, 9, 3])

    expect(tree.query(1)).toBe(3)
    expect(tree.query(2)).toBe(5)
    expect(tree.query(3)).toBe(4)
    expect(tree.query(4)).toBe(10)
    expect(tree.query(5)).toBe(15)
    expect(tree.query(6)).toBe(19)
    expect(tree.query(7)).toBe(16)
    expect(tree.query(8)).toBe(19)
    expect(tree.query(9)).toBe(26)
    expect(tree.query(10)).toBe(28)
    expect(tree.query(11)).toBe(31)

    expect(tree.queryRange(1, 1)).toBe(3)
    expect(tree.queryRange(1, 2)).toBe(5)
    expect(tree.queryRange(2, 4)).toBe(7)
    expect(tree.queryRange(6, 9)).toBe(11)

    tree.increase(3, 1)

    expect(tree.query(1)).toBe(3)
    expect(tree.query(2)).toBe(5)
    expect(tree.query(3)).toBe(5)
    expect(tree.query(4)).toBe(11)
    expect(tree.query(5)).toBe(16)
    expect(tree.query(6)).toBe(20)
    expect(tree.query(7)).toBe(17)
    expect(tree.query(8)).toBe(20)
    expect(tree.query(9)).toBe(27)
    expect(tree.query(10)).toBe(29)
    expect(tree.query(11)).toBe(32)

    expect(tree.queryRange(1, 1)).toBe(3)
    expect(tree.queryRange(1, 2)).toBe(5)
    expect(tree.queryRange(2, 4)).toBe(8)
    expect(tree.queryRange(6, 9)).toBe(11)
  })

  it('должен правильно выполнить запросы', () => {
    const tree = new FenwickTree(5)

    tree.increase(1, 4)
    tree.increase(3, 7)

    expect(tree.query(1)).toBe(4)
    expect(tree.query(3)).toBe(11)
    expect(tree.query(5)).toBe(11)
    expect(tree.queryRange(2, 3)).toBe(7)

    tree.increase(2, 5)
    expect(tree.query(5)).toBe(16)

    tree.increase(1, 3)
    expect(tree.queryRange(1, 1)).toBe(7)
    expect(tree.query(5)).toBe(19)
    expect(tree.queryRange(1, 5)).toBe(19)
  })

  it('должен выбросить исключения', () => {
    const tree = new FenwickTree(5)

    const increaseAtInvalidLowIndex = () => {
      tree.increase(0, 1)
    }

    const increaseAtInvalidHighIndex = () => {
      tree.increase(10, 1)
    }

    const queryInvalidLowIndex = () => {
      tree.query(0)
    }

    const queryInvalidHighIndex = () => {
      tree.query(10)
    }

    const rangeQueryInvalidIndex = () => {
      tree.queryRange(3, 2)
    }

    expect(increaseAtInvalidLowIndex).toThrowError()
    expect(increaseAtInvalidHighIndex).toThrowError()
    expect(queryInvalidLowIndex).toThrowError()
    expect(queryInvalidHighIndex).toThrowError()
    expect(rangeQueryInvalidIndex).toThrowError()
  })
})

Запускаем тесты:

npm run test ./data-structures/tree/__tests__/fenwick-tree

Результат:

14. Граф

Описание

• Википедия
• YouTube

Граф (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}`
}

Полный код узла графа:

// Связный список
import LinkedList from '../linked-list'

// Функция сравнения ребер
const edgeComparator = (a, b) => {
  if (a.getKey() === b.getKey()) {
    return 0
  }

  return a.getKey() < b.getKey() ? -1 : 1
}

// Функция преобразования соседних узлов
const convertNeighbors = (node) => {
  return node.value.from === this ? node.value.to : node.value.from
}

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(convertNeighbors)
  }

  // Возвращает список ребер в виде массива значений
  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()
  }
}

Проверяем, что код узла работает, как ожидается:

// data-structures/graph/__tests__/node.test.js
import Node from '../node'
import Edge from '../edge'

describe('Node', () => {
  it('должен выбросить исключение при создании узла без значения', () => {
    let node = null

    function createEmptyVertex() {
      node = new Node()
    }

    expect(node).toBeNull()
    expect(createEmptyVertex).toThrow()
  })

  it('должен создать узел графа', () => {
    const node = new Node('A')

    expect(node).toBeDefined()
    expect(node.value).toBe('A')
    expect(node.toString()).toBe('A')
    expect(node.getKey()).toBe('A')
    expect(node.edges.toString()).toBe('')
    expect(node.getEdges()).toEqual([])
  })

  it('должен добавить ребра в узел и определить их наличие', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.getEdges().length).toBe(1)
    expect(nodeA.getEdges()[0].toString()).toBe('A_B')
  })

  it('должен удалить определенные ребра из узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(2)

    expect(nodeA.getEdges()[0].toString()).toBe('A_B')
    expect(nodeA.getEdges()[1].toString()).toBe('A_C')

    nodeA.removeEdge(edgeAB)
    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeA.getEdges()[0].toString()).toBe('A_C')

    nodeA.removeEdge(edgeAC)
    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.hasEdge(edgeAC)).toBe(false)
    expect(nodeA.getEdges().length).toBe(0)
  })

  it('должна удалить все ребра из узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(2)

    nodeA.removeAllEdges()

    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(false)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(0)
  })

  it('должен вернуть соседей узла в случае, если текущий узел является начальным', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeB.getNeighbors()).toEqual([])

    const neighbors = nodeA.getNeighbors()

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен вернуть соседей узла в случае, если текущий узел является конечным', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeBA = new Edge(nodeB, nodeA)
    const edgeCA = new Edge(nodeC, nodeA)
    nodeA.addEdge(edgeBA).addEdge(edgeCA)

    expect(nodeB.getNeighbors()).toEqual([])

    const neighbors = nodeA.getNeighbors()

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен определить наличие соседнего узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.hasNeighbor(nodeB)).toBe(true)
    expect(nodeA.hasNeighbor(nodeC)).toBe(false)
  })

  it('должен найти ребро по узлу', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.findEdge(nodeB)).toEqual(edgeAB)
    expect(nodeA.findEdge(nodeC)).toBeNull()
  })

  it('должен вычислить глубину узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')

    expect(nodeA.getDegree()).toBe(0)

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.getDegree()).toBe(1)

    const edgeBA = new Edge(nodeB, nodeA)
    nodeA.addEdge(edgeBA)

    expect(nodeA.getDegree()).toBe(2)

    nodeA.addEdge(edgeAB)
    expect(nodeA.getDegree()).toBe(3)

    expect(nodeA.getEdges().length).toEqual(3)
  })
})

Запускаем тесты:

npm run test ./data-structures/graph/__tests__/node

Результат:

Проверяем, что код ребра работает, как ожидается:

// data-structures/graph/__tests__/edge.test.js
import Edge from '../edge'
import Node from '../node'

describe('Edge', () => {
  it('должена создать ребро графа с дефолтным весом', () => {
    const from = new Node('A')
    const to = new Node('B')
    const edge = new Edge(from, to)

    expect(edge.getKey()).toBe('A_B')
    expect(edge.toString()).toBe('A_B')
    expect(edge.from).toEqual(from)
    expect(edge.to).toEqual(to)
    expect(edge.weight).toEqual(0)
  })

  it('должена создать граф с указанным весом', () => {
    const from = new Node('A')
    const to = new Node('B')
    const edge = new Edge(from, to, 10)

    expect(edge.from).toEqual(from)
    expect(edge.to).toEqual(to)
    expect(edge.weight).toEqual(10)
  })

  it('должен инвертировать ребро', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const edge = new Edge(nodeA, nodeB, 10)

    expect(edge.from).toEqual(nodeA)
    expect(edge.to).toEqual(nodeB)
    expect(edge.weight).toEqual(10)

    edge.reverse()

    expect(edge.from).toEqual(nodeB)
    expect(edge.to).toEqual(nodeA)
    expect(edge.weight).toEqual(10)
  })
})

Запускаем тесты:

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()
}

Полный код графа:

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()
  }
}

Проверяем, что код графа работает, как ожидается:

// data-structures/graph/__tests__/graph.test.js
import Graph from '..'
import Node from '../node'
import Edge from '../edge'

describe('Graph', () => {
  it('должен добавить узлы в граф', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    graph.addNode(nodeA).addNode(nodeB)

    expect(graph.toString()).toBe('A,B')
    expect(graph.getNodeByKey(nodeA.getKey())).toEqual(nodeA)
    expect(graph.getNodeByKey(nodeB.getKey())).toEqual(nodeB)
  })

  it('должен добавить ребра в ненаправленный граф', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)

    graph.addEdge(edgeAB)

    expect(graph.getAllNodes().length).toBe(2)
    expect(graph.getAllNodes()[0]).toEqual(nodeA)
    expect(graph.getAllNodes()[1]).toEqual(nodeB)

    const graphNodeA = graph.getNodeByKey(nodeA.getKey())
    const graphNodeB = graph.getNodeByKey(nodeB.getKey())

    expect(graph.toString()).toBe('A,B')
    expect(graphNodeA).toBeDefined()
    expect(graphNodeB).toBeDefined()

    expect(graph.getNodeByKey('not existing')).toBeUndefined()

    expect(graphNodeA.getNeighbors().length).toBe(1)
    expect(graphNodeA.getNeighbors()[0]).toEqual(nodeB)
    expect(graphNodeA.getNeighbors()[0]).toEqual(graphNodeB)

    expect(graphNodeB.getNeighbors().length).toBe(1)
    expect(graphNodeB.getNeighbors()[0]).toEqual(nodeA)
    expect(graphNodeB.getNeighbors()[0]).toEqual(graphNodeA)
  })

  it('должен добавить ребра в направленный граф', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)

    graph.addEdge(edgeAB)

    const graphNodeA = graph.getNodeByKey(nodeA.getKey())
    const graphNodeB = graph.getNodeByKey(nodeB.getKey())

    expect(graph.toString()).toBe('A,B')
    expect(graphNodeA).toBeDefined()
    expect(graphNodeB).toBeDefined()

    expect(graphNodeA.getNeighbors().length).toBe(1)
    expect(graphNodeA.getNeighbors()[0]).toEqual(nodeB)
    expect(graphNodeA.getNeighbors()[0]).toEqual(graphNodeB)

    expect(graphNodeB.getNeighbors().length).toBe(0)
  })

  it('должен найти ребра по узлам в ненаправленном графе', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB, 10)

    graph.addEdge(edgeAB)

    const graphEdgeAB = graph.findEdge(nodeA, nodeB)
    const graphEdgeBA = graph.findEdge(nodeB, nodeA)
    const graphEdgeAC = graph.findEdge(nodeA, nodeC)
    const graphEdgeCA = graph.findEdge(nodeC, nodeA)

    expect(graphEdgeAC).toBeNull()
    expect(graphEdgeCA).toBeNull()
    expect(graphEdgeAB).toEqual(edgeAB)
    expect(graphEdgeBA).toEqual(edgeAB)
    expect(graphEdgeAB.weight).toBe(10)
  })

  it('должен найти ребра по узлам в направленном графе', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB, 10)

    graph.addEdge(edgeAB)

    const graphEdgeAB = graph.findEdge(nodeA, nodeB)
    const graphEdgeBA = graph.findEdge(nodeB, nodeA)
    const graphEdgeAC = graph.findEdge(nodeA, nodeC)
    const graphEdgeCA = graph.findEdge(nodeC, nodeA)

    expect(graphEdgeAC).toBeNull()
    expect(graphEdgeCA).toBeNull()
    expect(graphEdgeBA).toBeNull()
    expect(graphEdgeAB).toEqual(edgeAB)
    expect(graphEdgeAB.weight).toBe(10)
  })

  it('должен вернуть соседей узла', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeAC)

    const neighbors = graph.getNeighbors(nodeA)

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен выбросить исключение при повторном добавлении ребра', () => {
    function addSameEdgeTwice() {
      const graph = new Graph(true)

      const nodeA = new Node('A')
      const nodeB = new Node('B')

      const edgeAB = new Edge(nodeA, nodeB)

      graph.addEdge(edgeAB).addEdge(edgeAB)
    }

    expect(addSameEdgeTwice).toThrow()
  })

  it('должен вернуть список всех добавленных узлов', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeBC)

    const edges = graph.getAllEdges()

    expect(edges.length).toBe(2)
    expect(edges[0]).toEqual(edgeAB)
    expect(edges[1]).toEqual(edgeBC)
  })

  it('должен вычислить общий вес дефолтного графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeAD = new Edge(nodeA, nodeD)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeAD)

    expect(graph.getWeight()).toBe(0)
  })

  it('должен вычислить общий вес взвешенного графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB, 1)
    const edgeBC = new Edge(nodeB, nodeC, 2)
    const edgeCD = new Edge(nodeC, nodeD, 3)
    const edgeAD = new Edge(nodeA, nodeD, 4)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeAD)

    expect(graph.getWeight()).toBe(10)
  })

  it('должен удалить ребра из графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeAC = new Edge(nodeA, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeAC)

    expect(graph.getAllEdges().length).toBe(3)

    graph.removeEdge(edgeAB)

    expect(graph.getAllEdges().length).toBe(2)
    expect(graph.getAllEdges()[0].getKey()).toBe(edgeBC.getKey())
    expect(graph.getAllEdges()[1].getKey()).toBe(edgeAC.getKey())
  })

  it('должен выбросить исключение при удалении несуществующего узла', () => {
    function deleteNotExistingEdge() {
      const graph = new Graph()

      const nodeA = new Node('A')
      const nodeB = new Node('B')
      const nodeC = new Node('C')

      const edgeAB = new Edge(nodeA, nodeB)
      const edgeBC = new Edge(nodeB, nodeC)

      graph.addEdge(edgeAB)
      graph.removeEdge(edgeBC)
    }

    expect(deleteNotExistingEdge).toThrowError()
  })

  it('должен инвертировать граф', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)

    const graph = new Graph(true)
    graph.addEdge(edgeAB).addEdge(edgeAC).addEdge(edgeCD)

    expect(graph.toString()).toBe('A,B,C,D')
    expect(graph.getAllEdges().length).toBe(3)
    expect(graph.getNeighbors(nodeA).length).toBe(2)
    expect(graph.getNeighbors(nodeA)[0].getKey()).toBe(nodeB.getKey())
    expect(graph.getNeighbors(nodeA)[1].getKey()).toBe(nodeC.getKey())
    expect(graph.getNeighbors(nodeB).length).toBe(0)
    expect(graph.getNeighbors(nodeC).length).toBe(1)
    expect(graph.getNeighbors(nodeC)[0].getKey()).toBe(nodeD.getKey())
    expect(graph.getNeighbors(nodeD).length).toBe(0)

    graph.reverse()

    expect(graph.toString()).toBe('A,B,C,D')
    expect(graph.getAllEdges().length).toBe(3)
    expect(graph.getNeighbors(nodeA).length).toBe(0)
    expect(graph.getNeighbors(nodeB).length).toBe(1)
    expect(graph.getNeighbors(nodeB)[0].getKey()).toBe(nodeA.getKey())
    expect(graph.getNeighbors(nodeC).length).toBe(1)
    expect(graph.getNeighbors(nodeC)[0].getKey()).toBe(nodeA.getKey())
    expect(graph.getNeighbors(nodeD).length).toBe(1)
    expect(graph.getNeighbors(nodeD)[0].getKey()).toBe(nodeC.getKey())
  })

  it('должен вернуть индексы узлов', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeBD = new Edge(nodeB, nodeD)

    const graph = new Graph()
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const verticesIndices = graph.getNodesIndices()
    expect(verticesIndices).toEqual({
      A: 0,
      B: 1,
      C: 2,
      D: 3,
    })
  })

  it('должен вернуть матрицу смежности для ненаправленного графа', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeBD = new Edge(nodeB, nodeD)

    const graph = new Graph()
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const adjacencyMatrix = graph.getAdjacencyMatrix()
    expect(adjacencyMatrix).toEqual([
      [null, 0, null, null],
      [0, null, 0, 0],
      [null, 0, null, 0],
      [null, 0, 0, null],
    ])
  })

  it('должен вернуть матрицу смежности для направленного графа', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB, 2)
    const edgeBC = new Edge(nodeB, nodeC, 1)
    const edgeCD = new Edge(nodeC, nodeD, 5)
    const edgeBD = new Edge(nodeB, nodeD, 7)

    const graph = new Graph(true)
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const adjacencyMatrix = graph.getAdjacencyMatrix()
    expect(adjacencyMatrix).toEqual([
      [null, 2, null, null],
      [null, null, 1, 7],
      [null, null, null, 5],
      [null, null, null, null],
    ])
  })
})

Запускаем тесты:

npm run test ./data-structures/graph/__tests__/graph

Результат:

На сегодня это все, друзья. Увидимся в следующей части.

---

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩