javascript

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

  • пятница, 4 апреля 2025 г. в 00:00:10
https://habr.com/ru/companies/timeweb/articles/896800/


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


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


Сегодня мы поговорим об алгоритмах обхода связных списков и деревьев, а также начнем разбирать алгоритмы для работы с графами.


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


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



❯ Обход связного списка



Связным спискам посвящена первая часть серии.


❯ Прямой обход


Описание


Задача состоит в том, чтобы обойти (посетить каждый узел) связный список в прямом порядке (от головы до хвоста).


Например, для такого связного списка:





Порядок обхода будет следующим:


12 → 99 → 37

Сложность


Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить каждый узел и делаем это один раз.


Реализация


Реализация алгоритма до неприличия проста:


// algorithms/linked-lists/traverse.js
// Функция принимает связный список и обработчик посещения узла
export default function traverse(list, cb) {
  // Берем головной узел
  let node = list.head

  // Пока есть узлы
  while (node) {
    // Обрабатываем узел
    cb(node.value)
    // Берем следующий
    node = node.next
  }
}

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


// algorithms/linked-lists/__tests__/traverse.js
import LinkedList from '../../../data-structures/linked-list'
import traverse from '../traverse'

describe('traverse', () => {
  it('должен обойти связный список в прямом порядке', () => {
    const linkedList = new LinkedList()

    linkedList.append(1).append(2).append(3)

    const nodeValues = []
    const traversalCallback = (nodeValue) => {
      nodeValues.push(nodeValue)
    }

    traverse(linkedList, traversalCallback)

    expect(nodeValues).toEqual([1, 2, 3])
  })
})

❯ Обратный обход


Описание


Задача состоит в том, чтобы обойти (посетить каждый узел) связный список в обратном порядке (от хвоста до головы).


Например, для такого связного списка:





Порядок обхода будет следующим:


37 → 99 → 12

Сложность


Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить каждый узел и делаем это один раз.


Реализация


Для обхода списка в обратном порядке достаточно применить рекурсию:


// algorithms/linked-lists/reversal-traverse.js
// Функция принимает узел и обработчик его посещения
function reversalTraverseRecursive(node, cb) {
  // Пока есть узел
  if (node) {
    // Вызываем функцию со следующим узлом
    reversalTraverseRecursive(node.next, cb)
    // Обрабатываем узел
    cb(node.value)
  }
}

// Функция принимает связный список и обработчик посещения узла
export default function reversalTraverse(list, cb) {
  // Для того, чтобы понять рекурсию, надо сначала понять рекурсию :)
  reversalTraverseRecursive(list.head, cb)
}

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


// algorithms/linked-lists/__tests__/reversal-traverse.js
import LinkedList from '../../../data-structures/linked-list'
import reversalTraverse from '../reversal-traverse'

describe('reversalTraverse', () => {
  it('должен обойти связный список в обратном порядке', () => {
    const linkedList = new LinkedList()

    linkedList.append(1).append(2).append(3)

    const nodeValues = []
    const traversalCallback = (nodeValue) => {
      nodeValues.push(nodeValue)
    }

    reversalTraverse(linkedList, traversalCallback)

    expect(nodeValues).toEqual([3, 2, 1])
  })
})

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


npm run test ./algorithms/linked-lists/__tests__




❯ Обход дерева



Деревьям посвящены третья и четвертая части серии.


❯ Поиск в глубину


Описание



Поиск в глубину (depth-first search, DFS) — один из методов обхода дерева или графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины ребра. Если ребро ведет в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать ребра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось ребер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.





Сложность


Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить все узлы и делаем это один раз.


Реализация


Реализация данного алгоритма не отличается большой сложностью:


// algorithms/trees/depth-first-search.js
// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
  const initiatedCallbacks = {}
  const stubCallback = () => {}
  const defaultAllowTraverseCallback = () => true

  // Обработчик определения допустимости обхода
  initiatedCallbacks.allowTraverse =
    callbacks.allowTraverse || defaultAllowTraverseCallback
  // Обработчик вхождения в узел
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
  // Обработчик выхода из узла
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback

  return initiatedCallbacks
}

// Функция принимает узел и обработчики
function depthFirstSearchRecursive(node, callbacks) {
  // Вызываем обработчик вхождения в узел
  callbacks.enterNode(node)

  // Если имеется левый узел и его обход разрешен
  if (node.left && callbacks.allowTraverse(node, node.left)) {
    // Обходим левое поддерево
    depthFirstSearchRecursive(node.left, callbacks)
  }

  // Если имеется правый узел и его обход разрешен
  if (node.right && callbacks.allowTraverse(node, node.right)) {
    // Обходим правое поддерево
    depthFirstSearchRecursive(node.right, callbacks)
  }

  // Вызываем обработчик выхода из узла
  callbacks.leaveNode(node)
}

// Функция принимает начальный (корневой) узел и обработчики
export default function depthFirstSearch(root, callbacks) {
  // Инициализируем обработчики
  const _callbacks = initCallbacks(callbacks)
  // Запускаем рекурсию
  depthFirstSearchRecursive(root, _callbacks)
}

Тесты: 
// algorithms/trees/__tests__/depth-first-search.test.js
import BinaryTreeNode from '../../../data-structures/tree/binary-tree-node'
import depthFirstSearch from '../depth-first-search'

describe('depthFirstSearch', () => {
  it('должен обойти дерево в глубину', () => {
    const nodeA = new BinaryTreeNode('A')
    const nodeB = new BinaryTreeNode('B')
    const nodeC = new BinaryTreeNode('C')
    const nodeD = new BinaryTreeNode('D')
    const nodeE = new BinaryTreeNode('E')
    const nodeF = new BinaryTreeNode('F')
    const nodeG = new BinaryTreeNode('G')

    nodeA.setLeft(nodeB).setRight(nodeC)
    nodeB.setLeft(nodeD).setRight(nodeE)
    nodeC.setLeft(nodeF).setRight(nodeG)

    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим дерево с дефолтными обработчиками
    depthFirstSearch(nodeA)

    // Обходим дерево с кастомными обработчиками
    depthFirstSearch(nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(7)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(7)

    // Проверяем вход в узлы
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('B')
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('D')
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('E')
    expect(enterNodeCallback.mock.calls[4][0].value).toEqual('C')
    expect(enterNodeCallback.mock.calls[5][0].value).toEqual('F')
    expect(enterNodeCallback.mock.calls[6][0].value).toEqual('G')

    // Проверяем выход из узлов
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('D')
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('E')
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('B')
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('F')
    expect(leaveNodeCallback.mock.calls[4][0].value).toEqual('G')
    expect(leaveNodeCallback.mock.calls[5][0].value).toEqual('C')
    expect(leaveNodeCallback.mock.calls[6][0].value).toEqual('A')
  })

  it('должен проверить возможность кастомизации обработчиков', () => {
    const nodeA = new BinaryTreeNode('A')
    const nodeB = new BinaryTreeNode('B')
    const nodeC = new BinaryTreeNode('C')
    const nodeD = new BinaryTreeNode('D')
    const nodeE = new BinaryTreeNode('E')
    const nodeF = new BinaryTreeNode('F')
    const nodeG = new BinaryTreeNode('G')

    nodeA.setLeft(nodeB).setRight(nodeC)
    nodeB.setLeft(nodeD).setRight(nodeE)
    nodeC.setLeft(nodeF).setRight(nodeG)

    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим дерево с дефолтными обработчиками
    depthFirstSearch(nodeA)

    // Обходим дерево с кастомными обработчиками
    depthFirstSearch(nodeA, {
      allowTraverse: (node, child) => {
        // Запрещаем обход левой части дерева
        return child.value !== 'B'
      },
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(4)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(4)

    // Проверяем вход в узлы
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('C')
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('F')
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('G')

    // Проверяем выход из узлов
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('F')
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('G')
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('C')
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('A')
  })
})

❯ Поиск в ширину


Описание



Поиск в ширину (breadth-first search, BFS) — один из методов обхода графа. Пусть задан граф G=(V,E) и выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра G для "открытия" всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество ребер) от s до каждой достижимой вершины.


Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, то есть перед тем как приступить к поиску вершин на расстоянии k+1, выполняется обход вершин на расстоянии k.





Сложность


Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить все узлы и делаем это один раз.


Реализация


Для реализации данного алгоритма воспользуемся такой структурой данных, как очередь (queue):


// algorithms/trees/breadth-first-search.js
import Queue from '../../data-structures/queue'

// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
  const initiatedCallbacks = {}
  const stubCallback = () => {}
  const defaultAllowTraverseCallback = () => true

  // Обработчик определения допустимости обхода
  initiatedCallbacks.allowTraverse =
    callbacks.allowTraverse || defaultAllowTraverseCallback
  // Обработчик вхождения в узел
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
  // Обработчик выхода из узла
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback

  return initiatedCallbacks
}

// Функция принимает начальный (корневой) узел и обработчики
export default function breadthFirstSearch(root, callbacks) {
  // Инициализируем обработчики
  const _callbacks = initCallbacks(callbacks)
  // Создаем очередь
  const queue = new Queue()

  // Добавляем корневой узел в конец очереди
  queue.enqueue(root)

  // Пока в очереди есть элементы
  while (!queue.isEmpty()) {
    // Берем узел из начала очереди
    const node = queue.dequeue()

    // Вызываем обработчик вхождения в узел
    _callbacks.enterNode(node)

    // Если имеется левый узел и его обход разрешен
    if (node.left && _callbacks.allowTraverse(node, node.left)) {
      // Добавляем его в конец очереди
      queue.enqueue(node.left)
    }

    // Если имеется правый узел и его обход разрешен
    if (node.right && _callbacks.allowTraverse(node, node.right)) {
      // Добавляем его в конец очереди
      queue.enqueue(node.right)
    }

    // Вызываем обработчик выхода в узел
    _callbacks.leaveNode(node)
  }
}

Тесты: 
// algorithms/trees/__tests__/breadth-first-search.test.js
import BinaryTreeNode from '../../../data-structures/tree/binary-tree-node'
import breadthFirstSearch from '../breadth-first-search'

describe('breadthFirstSearch', () => {
  it('должен обойти дерево в ширину', () => {
    const nodeA = new BinaryTreeNode('A')
    const nodeB = new BinaryTreeNode('B')
    const nodeC = new BinaryTreeNode('C')
    const nodeD = new BinaryTreeNode('D')
    const nodeE = new BinaryTreeNode('E')
    const nodeF = new BinaryTreeNode('F')
    const nodeG = new BinaryTreeNode('G')

    nodeA.setLeft(nodeB).setRight(nodeC)
    nodeB.setLeft(nodeD).setRight(nodeE)
    nodeC.setLeft(nodeF).setRight(nodeG)

    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим дерево с дефолтными обработчиками
    breadthFirstSearch(nodeA)

    // Обходим дерево с кастомными обработчиками
    breadthFirstSearch(nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(7)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(7)

    // Проверяем вход в узлы
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('B')
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('C')
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('D')
    expect(enterNodeCallback.mock.calls[4][0].value).toEqual('E')
    expect(enterNodeCallback.mock.calls[5][0].value).toEqual('F')
    expect(enterNodeCallback.mock.calls[6][0].value).toEqual('G')

    // Проверяем выход из узлов
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('B')
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('C')
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('D')
    expect(leaveNodeCallback.mock.calls[4][0].value).toEqual('E')
    expect(leaveNodeCallback.mock.calls[5][0].value).toEqual('F')
    expect(leaveNodeCallback.mock.calls[6][0].value).toEqual('G')
  })

  it('должен проверить возможность кастомизации обработчиками', () => {
    const nodeA = new BinaryTreeNode('A')
    const nodeB = new BinaryTreeNode('B')
    const nodeC = new BinaryTreeNode('C')
    const nodeD = new BinaryTreeNode('D')
    const nodeE = new BinaryTreeNode('E')
    const nodeF = new BinaryTreeNode('F')
    const nodeG = new BinaryTreeNode('G')

    nodeA.setLeft(nodeB).setRight(nodeC)
    nodeB.setLeft(nodeD).setRight(nodeE)
    nodeC.setLeft(nodeF).setRight(nodeG)

    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим дерево с дефолтными обработчиками
    breadthFirstSearch(nodeA)

    // Обходим дерево с кастомными обработчиками
    breadthFirstSearch(nodeA, {
      allowTraverse: (_, child) => {
        // Запрещаем обход левой части дерева
        return child.value !== 'B'
      },
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(4)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(4)

    // Проверяем вход в узлы
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('C')
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('F')
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('G')

    // Проверяем выход из узлов
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('A')
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('C')
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('F')
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('G')
  })
})

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


npm run test ./algorithms/trees/__tests__




❯ Граф


Графам посвящена четвертая части серии.


❯ Поиск в глубину


Описание


См. "Обход дерева. Поиск в глубину".


Реализация


Разница между обходом дерева и обходом графа состоит в том, что в случае графа начальный узел выбирается произвольно. Это обуславливает необходимость отслеживания посещенных узлов:


// algorithms/graphs/depth-first-search.js
// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
  const initiatedCallbacks = {}
  const stubCallback = () => {}
  // Замыкание
  const defaultAllowTraverseCallback = (() => {
    // Посещенные узлы
    const traversed = {}
    return ({ nextNode }) => {
      // Пропускаем следующий узел, если он уже был посещен
      if (!traversed[nextNode.getKey()]) {
        traversed[nextNode.getKey()] = true
        return true
      }
      return false
    }
  })()
  initiatedCallbacks.allowTraverse =
    callbacks.allowTraverse || defaultAllowTraverseCallback
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback
  return initiatedCallbacks
}

// Функция принимает граф, текущий и предыдущий узлы, а также обработчики
function depthFirstSearchRecursive(
  graph,
  currentNode,
  previousNode,
  callbacks,
) {
  // Вызываем обработчик вхождения в узел
  callbacks.enterNode({ currentNode, previousNode })

  // Перебираем соседей текущего узла
  graph.getNeighbors(currentNode).forEach((nextNode) => {
    // Если узел не был посещен
    if (callbacks.allowTraverse({ previousNode, currentNode, nextNode })) {
      // Обходим его
      depthFirstSearchRecursive(graph, nextNode, currentNode, callbacks)
    }
  })

  // Вызываем обработчик выхода из узла
  callbacks.leaveNode({ currentNode, previousNode })
}

// Функция принимает граф, начальный узел и обработчики
export default function depthFirstSearch(graph, startNode, callbacks) {
  // Инициализируем обработчики
  const _callbacks = initCallbacks(callbacks)
  // Обходим граф
  depthFirstSearchRecursive(graph, startNode, null, _callbacks)
}

Тесты: 
// algorithms/graphs/__tests__/depth-first-search.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import depthFirstSearch from '../depth-first-search'

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

    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCG = new GraphEdge(nodeC, nodeG)
    const edgeAD = new GraphEdge(nodeA, nodeD)
    const edgeAE = new GraphEdge(nodeA, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)
    const edgeDG = new GraphEdge(nodeD, nodeG)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeCG)
      .addEdge(edgeAD)
      .addEdge(edgeAE)
      .addEdge(edgeEF)
      .addEdge(edgeFD)
      .addEdge(edgeDG)

    expect(graph.toString()).toBe('A,B,C,G,D,E,F')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим граф с дефолтными обработчиками
    depthFirstSearch(graph, nodeA)

    // Обходим граф с кастомными обработчиками
    depthFirstSearch(graph, nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(graph.getAllNodes().length)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(graph.getAllNodes().length)

    const enterNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeB, previousNode: nodeA },
      { currentNode: nodeC, previousNode: nodeB },
      { currentNode: nodeG, previousNode: nodeC },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeE, previousNode: nodeA },
      { currentNode: nodeF, previousNode: nodeE },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = enterNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        enterNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        enterNodeParamsMap[callIndex].previousNode,
      )
    }

    const leaveNodeParamsMap = [
      { currentNode: nodeG, previousNode: nodeC },
      { currentNode: nodeC, previousNode: nodeB },
      { currentNode: nodeB, previousNode: nodeA },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeF, previousNode: nodeE },
      { currentNode: nodeE, previousNode: nodeA },
      { currentNode: nodeA, previousNode: null },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = leaveNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        leaveNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        leaveNodeParamsMap[callIndex].previousNode,
      )
    }
  })

  it('должен проверить возможность кастомизации логики посещения узлов графа', () => {
    const graph = new Graph(true)

    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCG = new GraphEdge(nodeC, nodeG)
    const edgeAD = new GraphEdge(nodeA, nodeD)
    const edgeAE = new GraphEdge(nodeA, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)
    const edgeDG = new GraphEdge(nodeD, nodeG)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeCG)
      .addEdge(edgeAD)
      .addEdge(edgeAE)
      .addEdge(edgeEF)
      .addEdge(edgeFD)
      .addEdge(edgeDG)

    expect(graph.toString()).toBe('A,B,C,G,D,E,F')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    depthFirstSearch(graph, nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
      allowTraverse: ({ currentNode, nextNode }) => {
        return !(currentNode === nodeA && nextNode === nodeB)
      },
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(7)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(7)

    const enterNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeG, previousNode: nodeD },
      { currentNode: nodeE, previousNode: nodeA },
      { currentNode: nodeF, previousNode: nodeE },
      { currentNode: nodeD, previousNode: nodeF },
      { currentNode: nodeG, previousNode: nodeD },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = enterNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        enterNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        enterNodeParamsMap[callIndex].previousNode,
      )
    }

    const leaveNodeParamsMap = [
      { currentNode: nodeG, previousNode: nodeD },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeG, previousNode: nodeD },
      { currentNode: nodeD, previousNode: nodeF },
      { currentNode: nodeF, previousNode: nodeE },
      { currentNode: nodeE, previousNode: nodeA },
      { currentNode: nodeA, previousNode: null },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = leaveNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        leaveNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        leaveNodeParamsMap[callIndex].previousNode,
      )
    }
  })
})

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


npm run test ./algorithms/graphs/__tests__/depth-first-search




❯ Поиск в ширину


Описание


См. "Обход дерева. Поиск в ширину".


Реализация


Разница между обходом дерева и обходом графа состоит в том, что в случае графа начальный узел выбирается произвольно. Это обуславливает необходимость отслеживания посещенных узлов:


// algorithms/graphs/breadth-first-search.js
import Queue from '../../data-structures/queue'

// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
  const initiatedCallbacks = {}
  const stubCallback = () => {}
  // Замыкание
  const defaultAllowTraverseCallback = (() => {
    // Посещенные узлы
    const traversed = {}
    return ({ nextNode }) => {
      // Пропускаем следующий узел, если он уже был посещен
      if (!traversed[nextNode.getKey()]) {
        traversed[nextNode.getKey()] = true
        return true
      }
      return false
    }
  })()
  initiatedCallbacks.allowTraverse =
    callbacks.allowTraverse || defaultAllowTraverseCallback
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback
  return initiatedCallbacks
}

// Функция принимает граф, начальный узел и обработчики
export default function breadthFirstSearch(graph, startNode, callbacks) {
  // Инициализируем обработчики
  const _callbacks = initCallbacks(callbacks)
  // Создаем очередь
  const queue = new Queue()

  // Добавляем начальный узел в конец очереди
  queue.enqueue(startNode)

  let previousNode = null

  // Пока очередь не является пустой
  while (!queue.isEmpty()) {
    // Извлекаем узел из начала очереди
    const currentNode = queue.dequeue()

    // Вызываем обработчик вхождения в узел
    _callbacks.enterNode({ currentNode, previousNode })

    // Перебираем соседей текущего узла
    graph.getNeighbors(currentNode).forEach((nextNode) => {
      // Если посещение следующего узла разрешено
      if (_callbacks.allowTraverse({ previousNode, currentNode, nextNode })) {
        // Помещаем его в очередь
        queue.enqueue(nextNode)
      }
    })

    // Вызываем обработчик выхода из узла
    _callbacks.leaveNode({ currentNode, previousNode })

    // Запоминаем текущий узел перед следующей итерацией
    previousNode = currentNode
  }
}

Тесты: 
// algorithms/graphs/__tests__/breadth-first-search.test.js
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import GraphEdge from '../../../data-structures/graph/edge'
import breadthFirstSearch from '../breadth-first-search'

describe('breadthFirstSearch', () => {
  it('должен выполнить поиск в ширину по графу', () => {
    const graph = new Graph(true)

    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')
    const nodeH = new GraphNode('H')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCG = new GraphEdge(nodeC, nodeG)
    const edgeAD = new GraphEdge(nodeA, nodeD)
    const edgeAE = new GraphEdge(nodeA, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)
    const edgeDH = new GraphEdge(nodeD, nodeH)
    const edgeGH = new GraphEdge(nodeG, nodeH)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeCG)
      .addEdge(edgeAD)
      .addEdge(edgeAE)
      .addEdge(edgeEF)
      .addEdge(edgeFD)
      .addEdge(edgeDH)
      .addEdge(edgeGH)

    expect(graph.toString()).toBe('A,B,C,G,D,E,F,H')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Обходим граф с дефолтными обработчиками
    breadthFirstSearch(graph, nodeA)

    // Обходим граф с кастомными обработчиками
    breadthFirstSearch(graph, nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(8)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(8)

    const enterNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeB, previousNode: nodeA },
      { currentNode: nodeD, previousNode: nodeB },
      { currentNode: nodeE, previousNode: nodeD },
      { currentNode: nodeC, previousNode: nodeE },
      { currentNode: nodeH, previousNode: nodeC },
      { currentNode: nodeF, previousNode: nodeH },
      { currentNode: nodeG, previousNode: nodeF },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = enterNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        enterNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        enterNodeParamsMap[callIndex].previousNode,
      )
    }

    const leaveNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeB, previousNode: nodeA },
      { currentNode: nodeD, previousNode: nodeB },
      { currentNode: nodeE, previousNode: nodeD },
      { currentNode: nodeC, previousNode: nodeE },
      { currentNode: nodeH, previousNode: nodeC },
      { currentNode: nodeF, previousNode: nodeH },
      { currentNode: nodeG, previousNode: nodeF },
    ]

    for (
      let callIndex = 0;
      callIndex < graph.getAllNodes().length;
      callIndex += 1
    ) {
      const params = leaveNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        leaveNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        leaveNodeParamsMap[callIndex].previousNode,
      )
    }
  })

  it('должен проверить возможность кастомизации логики посещения узлов графа', () => {
    const graph = new Graph(true)

    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')
    const nodeH = new GraphNode('H')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCG = new GraphEdge(nodeC, nodeG)
    const edgeAD = new GraphEdge(nodeA, nodeD)
    const edgeAE = new GraphEdge(nodeA, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)
    const edgeDH = new GraphEdge(nodeD, nodeH)
    const edgeGH = new GraphEdge(nodeG, nodeH)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeCG)
      .addEdge(edgeAD)
      .addEdge(edgeAE)
      .addEdge(edgeEF)
      .addEdge(edgeFD)
      .addEdge(edgeDH)
      .addEdge(edgeGH)

    expect(graph.toString()).toBe('A,B,C,G,D,E,F,H')

    const enterNodeCallback = jest.fn()
    const leaveNodeCallback = jest.fn()

    // Traverse graph with enterNode and leaveNode callbacks.
    breadthFirstSearch(graph, nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
      allowTraverse: ({ currentNode, nextNode }) => {
        return !(currentNode === nodeA && nextNode === nodeB)
      },
    })

    expect(enterNodeCallback).toHaveBeenCalledTimes(7)
    expect(leaveNodeCallback).toHaveBeenCalledTimes(7)

    const enterNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeE, previousNode: nodeD },
      { currentNode: nodeH, previousNode: nodeE },
      { currentNode: nodeF, previousNode: nodeH },
      { currentNode: nodeD, previousNode: nodeF },
      { currentNode: nodeH, previousNode: nodeD },
    ]

    for (let callIndex = 0; callIndex < 7; callIndex += 1) {
      const params = enterNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        enterNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        enterNodeParamsMap[callIndex].previousNode,
      )
    }

    const leaveNodeParamsMap = [
      { currentNode: nodeA, previousNode: null },
      { currentNode: nodeD, previousNode: nodeA },
      { currentNode: nodeE, previousNode: nodeD },
      { currentNode: nodeH, previousNode: nodeE },
      { currentNode: nodeF, previousNode: nodeH },
      { currentNode: nodeD, previousNode: nodeF },
      { currentNode: nodeH, previousNode: nodeD },
    ]

    for (let callIndex = 0; callIndex < 7; callIndex += 1) {
      const params = leaveNodeCallback.mock.calls[callIndex][0]
      expect(params.currentNode).toEqual(
        leaveNodeParamsMap[callIndex].currentNode,
      )
      expect(params.previousNode).toEqual(
        leaveNodeParamsMap[callIndex].previousNode,
      )
    }
  })
})

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


npm run test ./algorithms/graphs/__tests__/breadth-first-search




❯ Алгоритм Краскала


Описание



Алгоритм Краскала (или Крускала, Kruskal's algorithm) — это эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.


Минимальное остовное (покрывающее) дерево (МОД) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него ребер.





Еще один пример графа и его МОД. Каждое ребро помечено весом, который здесь примерно пропорционален длине ребра:





На этом рисунке видно, что в графе может быть более одного МОД.


Принцип работы


В начале текущее множество ребер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех ребер, добавление которых к уже имеющемуся множеству не вызовет появление в нем цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких ребер больше нет, алгоритм завершен. Подграф данного графа, содержащий все его вершины и найденное множество ребер, является его МОД.


Сложность


До начала работы алгоритма необходимо отсортировать ребра по весу, это требует O(E × log(E)) времени, где E — множество ребер. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять ее за константу. Таким образом, общее время работы алгоритма Краскала можно принять за O(E * log(E)).





Демонстрация работы алгоритма Краскала на основе евклидова расстояния:





Реализация


В нашей реализации используются такие структуры данных, как граф (graph) и система непересекающихся множеств (disjoint set), а также алгоритм быстрой сортировки (quick sort):


// algorithms/graphs/kruskal.js
import DisjoinSet from '../../data-structures/disjoint-set/index'
import Graph from '../../data-structures/graph/index'
import QuickSort from '../sorting/quick-sort'

// Функция принимает граф
export default function kruskal(graph) {
  // При передаче направленного графа должно выбрасываться исключение
  if (graph.isDirected) {
    throw new Error(
      'Алгоритм Краскала работает только с ненаправленными графами',
    )
  }

  // Создаем новый граф, который будет содержать
  // минимальное остовное дерево исходного графа
  const minimumSpanningTree = new Graph()

  // Сортируем ребра графа в порядке возрастания веса
  const sortingCallbacks = {
    compareCallback: (a, b) => {
      if (a.weight === b.weight) {
        return 0
      }

      return a.weight < b.weight ? -1 : 1
    },
  }
  const sortedEdges = new QuickSort(sortingCallbacks).sort(graph.getAllEdges())

  // Создаем непересекающиеся одноэлементные множества для всех вершин графа
  const keyCb = (node) => node.getKey()
  const disjointSet = new DisjoinSet(keyCb)
  graph.getAllNodes().forEach((node) => disjointSet.makeSet(node))

  // Перебираем ребра графа, начиная с минимального, и пытаемся добавить их
  // в минимальное остовное дерево. Критерием добавления ребра является
  // формирование им цикла (если оно соединяет два узла одного подмножества)
  sortedEdges.forEach((edge) => {
    // Если добавление ребра не формирует цикл
    if (!disjointSet.isSameSet(edge.from, edge.to)) {
      // Объединяем два подмножества в одно
      disjointSet.union(edge.from, edge.to)

      // Добавляем ребро в дерево
      minimumSpanningTree.addEdge(edge)
    }
  })

  return minimumSpanningTree
}

Тесты: 
// algorithms/graphs/__tests__/kruskal.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import kruskal from '../kruskal'

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

      kruskal(graph)
    }

    expect(applyPrimToDirectedGraph).toThrowError()
  })

  it('должен найти минимальное остовное дерево', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')

    const edgeAB = new GraphEdge(nodeA, nodeB, 2)
    const edgeAD = new GraphEdge(nodeA, nodeD, 3)
    const edgeAC = new GraphEdge(nodeA, nodeC, 3)
    const edgeBC = new GraphEdge(nodeB, nodeC, 4)
    const edgeBE = new GraphEdge(nodeB, nodeE, 3)
    const edgeDF = new GraphEdge(nodeD, nodeF, 7)
    const edgeEC = new GraphEdge(nodeE, nodeC, 1)
    const edgeEF = new GraphEdge(nodeE, nodeF, 8)
    const edgeFG = new GraphEdge(nodeF, nodeG, 9)
    const edgeFC = new GraphEdge(nodeF, nodeC, 6)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeAD)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeBE)
      .addEdge(edgeDF)
      .addEdge(edgeEC)
      .addEdge(edgeEF)
      .addEdge(edgeFC)
      .addEdge(edgeFG)

    expect(graph.getWeight()).toEqual(46)

    const minimumSpanningTree = kruskal(graph)

    expect(minimumSpanningTree.getWeight()).toBe(24)
    expect(minimumSpanningTree.getAllNodes().length).toBe(
      graph.getAllNodes().length,
    )
    expect(minimumSpanningTree.getAllEdges().length).toBe(
      graph.getAllNodes().length - 1,
    )
    expect(minimumSpanningTree.toString()).toBe('E,C,A,B,D,F,G')
  })

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

    const edgeAB = new GraphEdge(nodeA, nodeB, 1)
    const edgeAD = new GraphEdge(nodeA, nodeD, 3)
    const edgeBC = new GraphEdge(nodeB, nodeC, 1)
    const edgeBD = new GraphEdge(nodeB, nodeD, 3)
    const edgeCD = new GraphEdge(nodeC, nodeD, 1)

    const graph = new Graph()

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

    expect(graph.getWeight()).toEqual(9)

    const minimumSpanningTree = kruskal(graph)

    expect(minimumSpanningTree.getWeight()).toBe(3)
    expect(minimumSpanningTree.getAllNodes().length).toBe(
      graph.getAllNodes().length,
    )
    expect(minimumSpanningTree.getAllEdges().length).toBe(
      graph.getAllNodes().length - 1,
    )
    expect(minimumSpanningTree.toString()).toBe('A,B,C,D')
  })
})

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


npm run test ./algorithms/graphs/__tests__/kruskal

Результат:





❯ Алгоритм Дейкстры


Описание



Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм для нахождения кратчайших путей от одной вершины графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса и широко применяется в программировании, например, в протоколах маршрутизации OSPF и IS-IS.


Принцип работы


Задача


Дан взвешенный ориентированный граф G(V,E) без ребер отрицательного веса. Необходимо найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.


Неформальное решение


Каждой вершине из множества вершин V сопоставим метку (вес) — минимальное известное расстояние от этой вершины до стартовой вершины a.


Алгоритм работает пошагово — на каждом шаге он "посещает" одну вершину и пытается уменьшать метки.


Работа алгоритма завершается, когда все вершины посещены.


Инициализация


Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности (Infinity).


Это отражает то, что расстояния от a до других вершин пока неизвестны.


Все вершины графа помечаются как непосещенные.


Шаг алгоритма


Если все вершины посещены, алгоритм завершается.


В противном случае, из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку.


Рассматриваем все возможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут ребра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещенные, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом.


Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.





Сложность алгоритма


Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.


В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d используется массив, время работы алгоритма составляет O(n^2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству ребер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма — O(n^2+m), но, так как m <= n(n-1), оно составляет O(n^2).


Реализация


Для реализации алгоритма используется такая структура данных, как очередь с приоритетом:


// algorithms/graphs/dijkstra.js
import PriorityQueue from '../../data-structures/priority-queue'

// Функция принимает граф и начальную вершину
export default function dijkstra(graph, startNode) {
  // Расстояния
  const distances = {}
  // Посещенные вершины
  const visited = {}
  // Предыдущие вершины
  const previous = {}

  const queue = new PriorityQueue()

  // Инициализируем все расстояния бесконечностью, предполагая, что
  // сейчас мы можем достичь только начальную вершину
  for (const node of graph.getAllNodes()) {
    distances[node.getKey()] = Infinity
    previous[node.getKey()] = null
  }

  // Мы находимся в начальной вершине, расстояние до нее равняется 0
  distances[startNode.getKey()] = 0

  // Добавляем текущую вершину в очередь
  queue.add(startNode, 0)

  // Перебираем вершины, пока очередь не опустеет
  while (!queue.isEmpty()) {
    // Извлекаем ближайшую вершину
    const current = queue.poll()

    // Перебираем непосещенных соседей текущей вершины
    current.getNeighbors().forEach((neighbor) => {
      // Если вершина еще не была посещена
      if (!visited[neighbor.getKey()]) {
        // Обновляем расстояние до каждого соседа
        const edge = graph.findEdge(current, neighbor)

        const existingDistanceToNeighbor = distances[neighbor.getKey()]
        const distanceFromNeighborToCurrent =
          distances[current.getKey()] + edge.weight

        // Если обнаружено более короткое расстояние
        if (distanceFromNeighborToCurrent < existingDistanceToNeighbor) {
          distances[neighbor.getKey()] = distanceFromNeighborToCurrent

          // Обновляем приоритет соседа в очереди, поскольку он может стать ближе
          if (queue.hasValue(neighbor)) {
            queue.changePriority(neighbor, distanceFromNeighborToCurrent)
          }

          // Обновляем предыдущую вершину
          previous[neighbor.getKey()] = current
        }

        // Добавляем соседа в очередь для дальнейшего посещения
        if (!queue.hasValue(neighbor)) {
          queue.add(neighbor, distances[neighbor.getKey()])
        }
      }
    })

    // Добавляем текущую вершину в посещенные во избежание повторного посещения
    visited[current.getKey()] = current
  }

  // Возвращаем набор кратчайших расстояний и
  // набор кратчайших путей ко всем вершинам графа
  return { distances, previous }
}

Обратите внимание: наш алгоритм умеет работать с графами, содержащими ребра отрицательного веса.


Тесты: 
// algorithms/graphs/__tests__/dijkstra.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import dijkstra from '../dijkstra'

describe('dijkstra', () => {
  it('должен найти минимальные пути до всех вершин ненаправленного графа', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')
    const nodeH = new GraphNode('H')

    const edgeAB = new GraphEdge(nodeA, nodeB, 4)
    const edgeAE = new GraphEdge(nodeA, nodeE, 7)
    const edgeAC = new GraphEdge(nodeA, nodeC, 3)
    const edgeBC = new GraphEdge(nodeB, nodeC, 6)
    const edgeBD = new GraphEdge(nodeB, nodeD, 5)
    const edgeEC = new GraphEdge(nodeE, nodeC, 8)
    const edgeED = new GraphEdge(nodeE, nodeD, 2)
    const edgeDC = new GraphEdge(nodeD, nodeC, 11)
    const edgeDG = new GraphEdge(nodeD, nodeG, 10)
    const edgeDF = new GraphEdge(nodeD, nodeF, 2)
    const edgeFG = new GraphEdge(nodeF, nodeG, 3)
    const edgeEG = new GraphEdge(nodeE, nodeG, 5)

    const graph = new Graph()
    graph
      .addNode(nodeH)
      .addEdge(edgeAB)
      .addEdge(edgeAE)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeBD)
      .addEdge(edgeEC)
      .addEdge(edgeED)
      .addEdge(edgeDC)
      .addEdge(edgeDG)
      .addEdge(edgeDF)
      .addEdge(edgeFG)
      .addEdge(edgeEG)

    const { distances, previous } = dijkstra(graph, nodeA)

    expect(distances).toEqual({
      H: Infinity,
      A: 0,
      B: 4,
      E: 7,
      C: 3,
      D: 9,
      G: 12,
      F: 11,
    })

    expect(previous.F.getKey()).toBe('D')
    expect(previous.D.getKey()).toBe('B')
    expect(previous.B.getKey()).toBe('A')
    expect(previous.G.getKey()).toBe('E')
    expect(previous.C.getKey()).toBe('A')
    expect(previous.A).toBeNull()
    expect(previous.H).toBeNull()
  })

  it('должен найти минимальные пути до всех вершин направленного графа с отрицательными весами ребер', () => {
    const nodeS = new GraphNode('S')
    const nodeE = new GraphNode('E')
    const nodeA = new GraphNode('A')
    const nodeD = new GraphNode('D')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeH = new GraphNode('H')

    const edgeSE = new GraphEdge(nodeS, nodeE, 8)
    const edgeSA = new GraphEdge(nodeS, nodeA, 10)
    const edgeED = new GraphEdge(nodeE, nodeD, 1)
    const edgeDA = new GraphEdge(nodeD, nodeA, -4)
    const edgeDC = new GraphEdge(nodeD, nodeC, -1)
    const edgeAC = new GraphEdge(nodeA, nodeC, 2)
    const edgeCB = new GraphEdge(nodeC, nodeB, -2)
    const edgeBA = new GraphEdge(nodeB, nodeA, 1)

    const graph = new Graph(true)
    graph
      .addNode(nodeH)
      .addEdge(edgeSE)
      .addEdge(edgeSA)
      .addEdge(edgeED)
      .addEdge(edgeDA)
      .addEdge(edgeDC)
      .addEdge(edgeAC)
      .addEdge(edgeCB)
      .addEdge(edgeBA)

    const { distances, previous } = dijkstra(graph, nodeS)

    expect(distances).toEqual({
      H: Infinity,
      S: 0,
      A: 5,
      B: 5,
      C: 7,
      D: 9,
      E: 8,
    })

    expect(previous.H).toBeNull()
    expect(previous.S).toBeNull()
    expect(previous.B.getKey()).toBe('C')
    expect(previous.C.getKey()).toBe('A')
    expect(previous.A.getKey()).toBe('D')
    expect(previous.D.getKey()).toBe('E')
  })
})

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


npm run test ./algorithms/graphs/__tests__/dijkstra




❯ Алгоритм Беллмана-Форда


Описание



Алгоритм Беллмана-Форда (Bellman-Ford algorithm) — это алгоритм поиска кратчайших путей от одной вершины графа до всех остальных во взвешенном графе. В отличие от алгоритма Дейкстры, данный алгоритм допускает ребра с отрицательным весом.


Алгоритм маршрутизации RIP (алгоритм Беллмана-Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.





Задача


Дан ориентированный или неориентированный граф G со взвешенными ребрами. Длиной пути назовем сумму весов ребер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.


Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов ребер которого отрицательна, называется отрицательным циклом.


Решение задачи будет зависеть от того, содержит ли граф отрицательные циклы.


Сложность


  • худшая временная — O(V x E), где V — множество вершин, а E — множество ребер
  • лучшая временная — O(E)
  • худшая пространственная — O(V)

Реализация


// algorithms/graphs/bellman-ford.js
// Функция принимает граф и начальную вершину
export default function bellmanFord(graph, startNode) {
  // Расстояния
  const distances = {}
  // Предыдущие вершины
  const previous = {}

  // Расстояние до начальной вершины равняется 0
  distances[startNode.getKey()] = 0
  // Все остальные расстояния равняются бесконечности
  graph.getAllNodes().forEach((node) => {
    if (node.getKey() !== startNode.getKey()) {
      distances[node.getKey()] = Infinity
    }
    previous[node.getKey()] = null
  })

  // Нам требуется `V - 1` итераций, где `V` - множество вершин
  for (let i = 0; i < graph.getAllNodes().length - 1; i++) {
    // Перебираем все вершины на каждой итерации
    Object.keys(distances).forEach((key) => {
      const node = graph.getNodeByKey(key)

      // Перебираем все ребра
      graph.getNeighbors(node).forEach((neighbor) => {
        const edge = graph.findEdge(node, neighbor)
        // Проверяем, является ли расстояние до соседа
        // на этой итерации меньше, чем на предыдущей
        const distanceToNeighbor = distances[node.getKey()] + edge.weight
        if (distanceToNeighbor < distances[neighbor.getKey()]) {
          distances[neighbor.getKey()] = distanceToNeighbor
          previous[neighbor.getKey()] = node
        }
      })
    })
  }

  return {
    distances,
    previous,
  }
}

Тесты: 
// algorithms/graphs/__tests__/bellman-ford.test.js
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import GraphEdge from '../../../data-structures/graph/edge'
import bellmanFord from '../bellman-ford'

describe('bellmanFord', () => {
  it('должен найти минимальные пути до всех вершин ненаправленного графа', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')
    const nodeG = new GraphNode('G')
    const nodeH = new GraphNode('H')

    const edgeAB = new GraphEdge(nodeA, nodeB, 4)
    const edgeAE = new GraphEdge(nodeA, nodeE, 7)
    const edgeAC = new GraphEdge(nodeA, nodeC, 3)
    const edgeBC = new GraphEdge(nodeB, nodeC, 6)
    const edgeBD = new GraphEdge(nodeB, nodeD, 5)
    const edgeEC = new GraphEdge(nodeE, nodeC, 8)
    const edgeED = new GraphEdge(nodeE, nodeD, 2)
    const edgeDC = new GraphEdge(nodeD, nodeC, 11)
    const edgeDG = new GraphEdge(nodeD, nodeG, 10)
    const edgeDF = new GraphEdge(nodeD, nodeF, 2)
    const edgeFG = new GraphEdge(nodeF, nodeG, 3)
    const edgeEG = new GraphEdge(nodeE, nodeG, 5)

    const graph = new Graph()
    graph
      .addNode(nodeH)
      .addEdge(edgeAB)
      .addEdge(edgeAE)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeBD)
      .addEdge(edgeEC)
      .addEdge(edgeED)
      .addEdge(edgeDC)
      .addEdge(edgeDG)
      .addEdge(edgeDF)
      .addEdge(edgeFG)
      .addEdge(edgeEG)

    const { distances, previous } = bellmanFord(graph, nodeA)

    expect(distances).toEqual({
      H: Infinity,
      A: 0,
      B: 4,
      E: 7,
      C: 3,
      D: 9,
      G: 12,
      F: 11,
    })

    expect(previous.F.getKey()).toBe('D')
    expect(previous.D.getKey()).toBe('B')
    expect(previous.B.getKey()).toBe('A')
    expect(previous.G.getKey()).toBe('E')
    expect(previous.C.getKey()).toBe('A')
    expect(previous.A).toBeNull()
    expect(previous.H).toBeNull()
  })

  it('должен найти минимальные пути до всех вершин направленного графа с ребрами отрицательного веса', () => {
    const nodeS = new GraphNode('S')
    const nodeE = new GraphNode('E')
    const nodeA = new GraphNode('A')
    const nodeD = new GraphNode('D')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeH = new GraphNode('H')

    const edgeSE = new GraphEdge(nodeS, nodeE, 8)
    const edgeSA = new GraphEdge(nodeS, nodeA, 10)
    const edgeED = new GraphEdge(nodeE, nodeD, 1)
    const edgeDA = new GraphEdge(nodeD, nodeA, -4)
    const edgeDC = new GraphEdge(nodeD, nodeC, -1)
    const edgeAC = new GraphEdge(nodeA, nodeC, 2)
    const edgeCB = new GraphEdge(nodeC, nodeB, -2)
    const edgeBA = new GraphEdge(nodeB, nodeA, 1)

    const graph = new Graph(true)
    graph
      .addNode(nodeH)
      .addEdge(edgeSE)
      .addEdge(edgeSA)
      .addEdge(edgeED)
      .addEdge(edgeDA)
      .addEdge(edgeDC)
      .addEdge(edgeAC)
      .addEdge(edgeCB)
      .addEdge(edgeBA)

    const { distances, previous } = bellmanFord(graph, nodeS)

    expect(distances).toEqual({
      H: Infinity,
      S: 0,
      A: 5,
      B: 5,
      C: 7,
      D: 9,
      E: 8,
    })

    expect(previous.H).toBeNull()
    expect(previous.S).toBeNull()
    expect(previous.B.getKey()).toBe('C')
    expect(previous.C.getKey()).toBe('A')
    expect(previous.A.getKey()).toBe('D')
    expect(previous.D.getKey()).toBe('E')
  })
})

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


npm run test ./algorithms/graphs/__tests__/bellman-ford




❯ Алгоритм Флойда-Уоршелла


Описание



Алгоритм Флойда-Уоршелла (Floyd-Warshall algorithm) — это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма.





Принцип работы


Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за O(V^3) сравнений в графе, даже если в графе может быть до V^2 ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.


Рассмотрим граф G с вершинами V, пронумерованными от 1 до N и функцию shortestPath(i, j, k), которая возвращает кратчайший возможный путь от i до j с использованием вершин только из множества {1, 2, ..., k} в качестве промежуточных точек на этом пути. Теперь, учитывая эту функцию, наша цель — найти кратчайший путь от каждого i до каждого j, используя любую вершину в {1, 2, ..., N}.





Эта формула является сердцем рассматриваемого алгоритма.


Пример


Пример выполнения алгоритма на графе слева внизу:





Матрица расстояний на каждой итерации k (обновленные расстояния выделены жирным шрифтом) будет иметь вид:


k = 0


1 2 3 4
1 0 ∞ −2 ∞
2 4 0 3 ∞
3 ∞ ∞ 0 2
4 ∞ −1 ∞ 0

k = 1


1 2 3 4
1 0 ∞ −2 ∞
2 4 0 2 ∞
3 ∞ ∞ 0 2
4 ∞ − ∞ 0

k = 2


1 2 3 4
1 0 ∞ −2 ∞
2 4 0 2 ∞
3 ∞ ∞ 0 2
4 3 −1 1 0

k = 3


1 2 3 4
1 0 ∞ −2 0
2 4 0 2 4
3 ∞ ∞ 0 2
4 3 −1 1 0

k = 4


1 2 3 4
1 0 −1 −2 0
2 4 0 2 4
3 5 1 0 2
4 3 −1 1 0

Реализация


// algorithms/graphs/floyd-warshall.js
// Функция принимает граф
export default function floydWarshall(graph) {
  // Извлекаем все вершины
  const vertices = graph.getAllNodes()

  // Инициализируем матрицу предыдущих вершин
  const nextVertices = Array(vertices.length)
    .fill(null)
    .map(() => {
      return Array(vertices.length).fill(null)
    })

  // Инициализируем матрицу расстояний
  const distances = Array(vertices.length)
    .fill(null)
    .map(() => {
      return Array(vertices.length).fill(Infinity)
    })

  // Инициализируем `distances` расстояниями,
  // которые нам уже известны (из имеющихся ребер).
  // Также инициализируем матрицу предыдущих вершин
  vertices.forEach((startVertex, startIndex) => {
    vertices.forEach((endVertex, endIndex) => {
      if (startVertex === endVertex) {
        // Расстояние вершины до самой себя составляет 0
        distances[startIndex][endIndex] = 0
      } else {
        // Находим ребро между начальной и конечной вершинами
        const edge = graph.findEdge(startVertex, endVertex)

        // Если такое ребро имеется
        if (edge) {
          // Сохраняем расстояние и предыдущую вершину
          distances[startIndex][endIndex] = edge.weight
          nextVertices[startIndex][endIndex] = startVertex
        } else {
          distances[startIndex][endIndex] = Infinity
        }
      }
    })
  })

  // Переходим к основной части алгоритма.
  // Объединяем все вершины в пары (от начала до конца) и проверяем,
  // существует ли между ними более короткий путь через среднюю вершину.
  // Средняя вершина также может быть одной из вершин графа.
  // Таким образом, нам требуется три цикла по всем вершинам графа:
  // для начальной, конечной и средней вершин
  vertices.forEach((middleVertex, middleIndex) => {
    // Путь начинается от `startVertex` с `startIndex`
    vertices.forEach((_startVertex, startIndex) => {
      // Путь заканчивается `endVertex` с `endIndex`
      vertices.forEach((_endVertex, endIndex) => {
        // Сравниваем существующее расстояние от `startVertex` до `endVertex`,
        // с расстоянием от `startVertex` до `endVertex`, но через `middleVertex`.
        // Сохраняем кратчайшее расстояние и предыдущую вершину,
        // предоставляющую этот кратчайший путь
        const distViaMiddle =
          distances[startIndex][middleIndex] + distances[middleIndex][endIndex]

        if (distances[startIndex][endIndex] > distViaMiddle) {
          // Мы нашли более короткий путь через `middleVertex`
          distances[startIndex][endIndex] = distViaMiddle
          nextVertices[startIndex][endIndex] = middleVertex
        }
      })
    })
  })

  // Кратчайшее расстояние от `x` до `y`: `distance[x][y]`.
  // Следующая вершина после `x` на пути от `x` до `y`: `nextVertices[x][y]`
  return { distances, nextVertices }
}

Тестирование: 
// algorithms/graphs/__tests__/floyd-warshall.test.js
import Graph from '../../../data-structures/graph/Graph'
import GraphEdge from '../../../data-structures/graph/GraphEdge'
import GraphVertex from '../../../data-structures/graph/GraphVertex'
import floydWarshall from '../floyd-warshall'

describe('floydWarshall', () => {
  it('должен найти минимальные пути для всех вершин ненаправленного графа', () => {
    const vertexA = new GraphVertex('A')
    const vertexB = new GraphVertex('B')
    const vertexC = new GraphVertex('C')
    const vertexD = new GraphVertex('D')
    const vertexE = new GraphVertex('E')
    const vertexF = new GraphVertex('F')
    const vertexG = new GraphVertex('G')
    const vertexH = new GraphVertex('H')

    const edgeAB = new GraphEdge(vertexA, vertexB, 4)
    const edgeAE = new GraphEdge(vertexA, vertexE, 7)
    const edgeAC = new GraphEdge(vertexA, vertexC, 3)
    const edgeBC = new GraphEdge(vertexB, vertexC, 6)
    const edgeBD = new GraphEdge(vertexB, vertexD, 5)
    const edgeEC = new GraphEdge(vertexE, vertexC, 8)
    const edgeED = new GraphEdge(vertexE, vertexD, 2)
    const edgeDC = new GraphEdge(vertexD, vertexC, 11)
    const edgeDG = new GraphEdge(vertexD, vertexG, 10)
    const edgeDF = new GraphEdge(vertexD, vertexF, 2)
    const edgeFG = new GraphEdge(vertexF, vertexG, 3)
    const edgeEG = new GraphEdge(vertexE, vertexG, 5)

    const graph = new Graph()

    // Сначала добавляем вершины в правильном порядке
    graph
      .addNode(vertexA)
      .addNode(vertexB)
      .addNode(vertexC)
      .addNode(vertexD)
      .addNode(vertexE)
      .addNode(vertexF)
      .addNode(vertexG)
      .addNode(vertexH)

    // Теперь добавляем ребра
    graph
      .addEdge(edgeAB)
      .addEdge(edgeAE)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeBD)
      .addEdge(edgeEC)
      .addEdge(edgeED)
      .addEdge(edgeDC)
      .addEdge(edgeDG)
      .addEdge(edgeDF)
      .addEdge(edgeFG)
      .addEdge(edgeEG)

    const { distances, nextVertices } = floydWarshall(graph)

    const vertices = graph.getAllNodes()

    const vertexAIndex = vertices.indexOf(vertexA)
    const vertexBIndex = vertices.indexOf(vertexB)
    const vertexCIndex = vertices.indexOf(vertexC)
    const vertexDIndex = vertices.indexOf(vertexD)
    const vertexEIndex = vertices.indexOf(vertexE)
    const vertexFIndex = vertices.indexOf(vertexF)
    const vertexGIndex = vertices.indexOf(vertexG)
    const vertexHIndex = vertices.indexOf(vertexH)

    expect(distances[vertexAIndex][vertexHIndex]).toBe(Infinity)
    expect(distances[vertexAIndex][vertexAIndex]).toBe(0)
    expect(distances[vertexAIndex][vertexBIndex]).toBe(4)
    expect(distances[vertexAIndex][vertexEIndex]).toBe(7)
    expect(distances[vertexAIndex][vertexCIndex]).toBe(3)
    expect(distances[vertexAIndex][vertexDIndex]).toBe(9)
    expect(distances[vertexAIndex][vertexGIndex]).toBe(12)
    expect(distances[vertexAIndex][vertexFIndex]).toBe(11)

    expect(nextVertices[vertexAIndex][vertexFIndex]).toBe(vertexD)
    expect(nextVertices[vertexAIndex][vertexDIndex]).toBe(vertexB)
    expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexA)
    expect(nextVertices[vertexAIndex][vertexGIndex]).toBe(vertexE)
    expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexA)
    expect(nextVertices[vertexAIndex][vertexAIndex]).toBe(null)
    expect(nextVertices[vertexAIndex][vertexHIndex]).toBe(null)
  })

  it('должен найти минимальные пути для всех вершин направленного графа', () => {
    const vertexA = new GraphVertex('A')
    const vertexB = new GraphVertex('B')
    const vertexC = new GraphVertex('C')
    const vertexD = new GraphVertex('D')

    const edgeAB = new GraphEdge(vertexA, vertexB, 3)
    const edgeBA = new GraphEdge(vertexB, vertexA, 8)
    const edgeAD = new GraphEdge(vertexA, vertexD, 7)
    const edgeDA = new GraphEdge(vertexD, vertexA, 2)
    const edgeBC = new GraphEdge(vertexB, vertexC, 2)
    const edgeCA = new GraphEdge(vertexC, vertexA, 5)
    const edgeCD = new GraphEdge(vertexC, vertexD, 1)

    const graph = new Graph(true)

    graph
      .addNode(vertexA)
      .addNode(vertexB)
      .addNode(vertexC)
      .addNode(vertexD)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBA)
      .addEdge(edgeAD)
      .addEdge(edgeDA)
      .addEdge(edgeBC)
      .addEdge(edgeCA)
      .addEdge(edgeCD)

    const { distances, nextVertices } = floydWarshall(graph)

    const vertices = graph.getAllNodes()

    const vertexAIndex = vertices.indexOf(vertexA)
    const vertexBIndex = vertices.indexOf(vertexB)
    const vertexCIndex = vertices.indexOf(vertexC)
    const vertexDIndex = vertices.indexOf(vertexD)

    expect(distances[vertexAIndex][vertexAIndex]).toBe(0)
    expect(distances[vertexAIndex][vertexBIndex]).toBe(3)
    expect(distances[vertexAIndex][vertexCIndex]).toBe(5)
    expect(distances[vertexAIndex][vertexDIndex]).toBe(6)

    expect(distances).toEqual([
      [0, 3, 5, 6],
      [5, 0, 2, 3],
      [3, 6, 0, 1],
      [2, 5, 7, 0],
    ])

    expect(nextVertices[vertexAIndex][vertexDIndex]).toBe(vertexC)
    expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexB)
    expect(nextVertices[vertexBIndex][vertexDIndex]).toBe(vertexC)
    expect(nextVertices[vertexAIndex][vertexAIndex]).toBe(null)
    expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexA)
  })

  it('должен найти минимальные пути для всех вершин направленного графа с отрицательными весами ребер', () => {
    const vertexA = new GraphVertex('A')
    const vertexB = new GraphVertex('B')
    const vertexC = new GraphVertex('C')
    const vertexD = new GraphVertex('D')
    const vertexE = new GraphVertex('E')
    const vertexF = new GraphVertex('F')
    const vertexG = new GraphVertex('G')

    const edgeFE = new GraphEdge(vertexF, vertexE, 8)
    const edgeFA = new GraphEdge(vertexF, vertexA, 10)
    const edgeED = new GraphEdge(vertexE, vertexD, 1)
    const edgeDA = new GraphEdge(vertexD, vertexA, -4)
    const edgeDC = new GraphEdge(vertexD, vertexC, -1)
    const edgeAC = new GraphEdge(vertexA, vertexC, 2)
    const edgeCB = new GraphEdge(vertexC, vertexB, -2)
    const edgeBA = new GraphEdge(vertexB, vertexA, 1)

    const graph = new Graph(true)

    graph
      .addNode(vertexA)
      .addNode(vertexB)
      .addNode(vertexC)
      .addNode(vertexD)
      .addNode(vertexE)
      .addNode(vertexF)
      .addNode(vertexG)

    graph
      .addEdge(edgeFE)
      .addEdge(edgeFA)
      .addEdge(edgeED)
      .addEdge(edgeDA)
      .addEdge(edgeDC)
      .addEdge(edgeAC)
      .addEdge(edgeCB)
      .addEdge(edgeBA)

    const { distances, nextVertices } = floydWarshall(graph)

    const vertices = graph.getAllNodes()

    const vertexAIndex = vertices.indexOf(vertexA)
    const vertexBIndex = vertices.indexOf(vertexB)
    const vertexCIndex = vertices.indexOf(vertexC)
    const vertexDIndex = vertices.indexOf(vertexD)
    const vertexEIndex = vertices.indexOf(vertexE)
    const vertexGIndex = vertices.indexOf(vertexG)
    const vertexFIndex = vertices.indexOf(vertexF)

    expect(distances[vertexFIndex][vertexGIndex]).toBe(Infinity)
    expect(distances[vertexFIndex][vertexFIndex]).toBe(0)
    expect(distances[vertexFIndex][vertexAIndex]).toBe(5)
    expect(distances[vertexFIndex][vertexBIndex]).toBe(5)
    expect(distances[vertexFIndex][vertexCIndex]).toBe(7)
    expect(distances[vertexFIndex][vertexDIndex]).toBe(9)
    expect(distances[vertexFIndex][vertexEIndex]).toBe(8)

    expect(nextVertices[vertexFIndex][vertexGIndex]).toBe(null)
    expect(nextVertices[vertexFIndex][vertexFIndex]).toBe(null)
    expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexC)
    expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexA)
    expect(nextVertices[vertexFIndex][vertexBIndex]).toBe(vertexE)
    expect(nextVertices[vertexEIndex][vertexBIndex]).toBe(vertexD)
    expect(nextVertices[vertexDIndex][vertexBIndex]).toBe(vertexC)
    expect(nextVertices[vertexCIndex][vertexBIndex]).toBe(vertexC)
  })
})

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


npm run test ./algorithms/graphs/__tests__/floyd-warshall




❯ Определение цикла


Описание


Общая информация



Циклы в ненаправленных графах



Циклы в направленных графах



В теории графов два типа объектов обычно называются циклами.


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



Граф с окрашенными ребрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения ребер или вершин H-D-G-H


Поиск цикла


Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещенной вершине (обратная дуга). Таким же образом, все обратные ребра, которые алгоритм DFS обнаруживает, являются частями циклов. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 ребер могут быть ребрами дерева.


Ориентированный граф имеет цикл в том и только в том случае, когда DFS находит обратную дугу. Дуги вперед и поперечные дуги не обязательно говорят о цикле. Многие алгоритмы топологических сортировок также обнаруживают циклы, поскольку они мешают существованию топологического порядка. Если ориентированный граф разделен на компоненты сильной связности, циклы существуют только в компонентах, но не между ними, поскольку циклы сильно связаны.


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


Определение цикла в неориентированном графе


Реализация


Цикл в ненаправленном графе можно обнаружить, как минимум, двумя способами.


С помощью поиска в глубину (DFS):


// algorithms/graphs/detect-cycle/undirected.js
import depthFirstSearch from '../depth-first-search'

// Функция принимает граф
export default function detectUndirectedCycle(graph) {
  let cycle = null

  // Список посещенных узлов
  const visited = {}

  // Список предков каждого посещенного узла
  const parents = {}

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode, previousNode }) => {
      // Если узел уже посещен, то обнаружен цикл
      if (visited[currentNode.getKey()]) {
        // Вычисляем его путь
        cycle = {}

        let current = currentNode
        let previous = previousNode

        while (currentNode.getKey() !== previous.getKey()) {
          cycle[current.getKey()] = previous
          current = previous
          previous = parents[previous.getKey()]
        }

        cycle[current.getKey()] = previous
      } else {
        // Добавляем текущий узел в посещенные
        visited[currentNode.getKey()] = currentNode
        // Обновляем список предков
        parents[currentNode.getKey()] = previousNode
      }
    },
    // Обработчик определения допустимости обхода
    allowTraverse: ({ currentNode, nextNode }) => {
      // Запрещаем обход цикла
      if (cycle) {
        return false
      }

      // Запрещаем возвращаться к предку
      const currentNodeParent = parents[currentNode.getKey()]

      return currentNodeParent?.getKey() !== nextNode.getKey()
    },
  }

  // Берем первый узел
  const startNode = graph.getAllNodes()[0]
  // Запускаем поиск в глубину
  depthFirstSearch(graph, startNode, callbacks)

  return cycle
}

Тесты: 
// algorithms/graphs/detect-cycle/__tests__/undirected.test.js
import GraphEdge from '../../../../data-structures/graph/edge'
import Graph from '../../../../data-structures/graph/index'
import GraphNode from '../../../../data-structures/graph/node'
import detectUndirectedCycle from '../undirected'

describe('detectUndirectedCycle', () => {
  it('должен обнаружить цикл в ненаправленном графе', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')

    const edgeAF = new GraphEdge(nodeA, nodeF)
    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBE = new GraphEdge(nodeB, nodeE)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)

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

    expect(detectUndirectedCycle(graph)).toBeNull()

    graph.addEdge(edgeDE)

    expect(detectUndirectedCycle(graph)).toEqual({
      B: nodeC,
      C: nodeD,
      D: nodeE,
      E: nodeB,
    })
  })
})

С помощью системы непересекающихся множеств (disjoint set):


// algorithms/graphs/detect-cycle/undirected-disjoint-set.js
import DisjoinSet from '../../../data-structures/disjoint-set'

export default function detectUndirectedCycleUsingDisjointSet(graph) {
  // Создаем непересекающиеся одноэлементные множества для каждого узла графа
  const keyExtractor = (node) => node.getKey()
  const disjointSet = new DisjoinSet(keyExtractor)
  graph.getAllNodes().forEach((node) => disjointSet.makeSet(node))

  // Перебираем все ребра графа и проверяем, что узлы ребра принадлежат
  // разным множествам. В этом случае объединяем множества. Делаем это
  // до обнаружения узлов, которые принадлежат обоим множествам. Это
  // означает обнаружение цикла
  let cycle = false
  graph.getAllEdges().forEach((edge) => {
    if (disjointSet.isSameSet(edge.from, edge.to)) {
      cycle = true
    } else {
      disjointSet.union(edge.from, edge.to)
    }
  })

  return cycle
}

Тесты: 
// algorithms/graphs/detect-cycle/__tests__/undirected-disjoint-set.test.js
import GraphEdge from '../../../../data-structures/graph/edge'
import Graph from '../../../../data-structures/graph/index'
import GraphNode from '../../../../data-structures/graph/node'
import detectUndirectedCycleUsingDisjointSet from '../undirected-disjoint-set'

describe('detectUndirectedCycleUsingDisjointSet', () => {
  it('должен обнаружить цикл в ненаправленном графе', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')

    const edgeAF = new GraphEdge(nodeA, nodeF)
    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBE = new GraphEdge(nodeB, nodeE)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)

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

    expect(detectUndirectedCycleUsingDisjointSet(graph)).toBe(false)

    graph.addEdge(edgeDE)

    expect(detectUndirectedCycleUsingDisjointSet(graph)).toBe(true)
  })
})

Алгоритм определения цикла в направленном графе также можно реализовать с помощью поиска в глубину:


// algorithms/graphs/detect-cycle/__tests__/directed.test.js
import depthFirstSearch from '../depth-first-search'

export default function detectDirectedCycle(graph) {
  let cycle = null

  // Список предков каждого посещенного узла
  const parents = {}

  // Белый набор содержит узлы, которые еще не посещались
  const whiteSet = {}

  // Серый набор содержит узлы, которые посещаются сейчас (на текущем пути)
  const graySet = {}

  // Черный набор содержит узлы, которые полностью посещены.
  // Это означает, что были посещены все потомки узла
  const blackSet = {}

  // Обнаружение узла в сером наборе означает, что обнаружен цикл.
  // Если узел находится в сером наборе, значит,
  // его соседи или соседи его соседей сейчас посещаются

  // Инициализируем белый набор
  graph.getAllNodes().forEach((node) => {
    whiteSet[node.getKey()] = node
  })

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode, previousNode }) => {
      // Если узел находится в сером наборе, значит, обнаружен цикл
      if (graySet[currentNode.getKey()]) {
        // Вычисляем его путь
        cycle = {}

        let current = currentNode
        let previous = previousNode

        while (currentNode.getKey() !== previous.getKey()) {
          cycle[current.getKey()] = previous
          current = previous
          previous = parents[previous.getKey()]
        }

        cycle[current.getKey()] = previous
      } else {
        // Добавляем текущий узел в серый набор и удаляем его из белого набора
        graySet[currentNode.getKey()] = currentNode
        delete whiteSet[currentNode.getKey()]

        // Обновляем список предков
        parents[currentNode.getKey()] = previousNode
      }
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode }) => {
      // Если все потомки узла были посещены, удаляем его из серого набора
      // и добавляем в черный набор
      blackSet[currentNode.getKey()] = currentNode
      delete graySet[currentNode.getKey()]
    },
    // Обработчик определения допустимости обхода
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход цикла
      if (cycle) {
        return false
      }

      // Запрещаем обход черных узлов
      return !blackSet[nextNode.getKey()]
    },
  }

  // Пока в белом наборе есть узлы
  while (Object.keys(whiteSet).length) {
    // Берем первый узел
    const firstKey = Object.keys(whiteSet)[0]
    const startNode = whiteSet[firstKey]
    // Запускаем поиск в глубину
    depthFirstSearch(graph, startNode, callbacks)
  }

  return cycle
}

Тесты: 
// algorithms/graphs/detect-cycle/__tests__/directed.test.js
import GraphEdge from '../../../../data-structures/graph/edge'
import Graph from '../../../../data-structures/graph/index'
import GraphNode from '../../../../data-structures/graph/node'
import detectDirectedCycle from '../directed'

describe('detectDirectedCycle', () => {
  it('должен обнаружить цикл в направленном графе', () => {
    const nodeA = new GraphNode('A')
    const nodeB = new GraphNode('B')
    const nodeC = new GraphNode('C')
    const nodeD = new GraphNode('D')
    const nodeE = new GraphNode('E')
    const nodeF = new GraphNode('F')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeDA = new GraphEdge(nodeD, nodeA)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)

    const graph = new Graph(true)
    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeDA)
      .addEdge(edgeDE)
      .addEdge(edgeEF)

    expect(detectDirectedCycle(graph)).toBeNull()

    graph.addEdge(edgeFD)

    expect(detectDirectedCycle(graph)).toEqual({
      D: nodeF,
      F: nodeE,
      E: nodeD,
    })
  })
})

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


npm run test ./algorithms/graphs/detect-cycle/__tests__




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




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