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

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

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

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

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

• Первая часть
• Вторая часть
• Третья часть
• Четвертая часть
• Пятая часть
• Шестая часть
• Седьмая часть
• Восьмая часть
• Девятая часть

❯ Граф

❯ Алгоритм Прима

Описание

• Википедия — алгоритм Прима
• Википедия — минимальное остовное дерево
• YouTube

Алгоритм Прима (Prim's algorithm) — это алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

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

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

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

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

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

Сначала берется произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются ребра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих ребер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является МОД.

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

Псевдокод

Сложность

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь Q реализована как обычный массив d, то Extract.Min(Q) выполняется за O(n), а стоимость операции d|u| <- w(v, u) составляет O(1). Если Q представляет собой бинарную пирамиду, то стоимость Extract.Min(Q) снижается до O(log n), а стоимость d|u| <- w(v, u) возрастает до O(log n). При использовании фибоначчиевых пирамид операция Extract.Min(Q) выполняется за O(log n), а d|u| <- w(v, u) — за O(1).

Реализация

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

// algorithms/graphs/prim.js
import Graph from '../../data-structures/graph/index'
import PriorityQueue from '../../data-structures/priority-queue'

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

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

  // Эта очередь с приоритетом будет содержать все ребра,
  // начинающиеся от посещенных узлов и ранжированные по весу -
  // на каждом шаге мы всегда будем получать ребро с минимальным весом
  const edgesQueue = new PriorityQueue()

  // Набор посещенных узлов
  const visited = {}

  // Начальный узел для обхода графа
  const startNode = graph.getAllNodes()[0]

  // Добавляем начальный узел в набор посещенных узлов
  visited[startNode.getKey()] = startNode

  // Добавляем все ребра начального узла в очередь
  startNode.getEdges().forEach((graphEdge) => {
    edgesQueue.add(graphEdge, graphEdge.weight)
  })

  // Перебираем ребра, находящиеся в очереди
  while (!edgesQueue.isEmpty()) {
    // Извлекаем следующее ребро с минимальным весом
    const currentMinEdge = edgesQueue.poll()

    // Находим следующий непосещенный минимальный узел для обхода
    let nextMinNode = null
    if (!visited[currentMinEdge.from.getKey()]) {
      nextMinNode = currentMinEdge.from
    } else if (!visited[currentMinEdge.to.getKey()]) {
      nextMinNode = currentMinEdge.to
    }

    // Пропускаем итерацию, если все узлы текущего ребра уже посещены
    if (nextMinNode) {
      // Добавляем текущее минимальное ребро в МОД
      minimumSpanningTree.addEdge(currentMinEdge)

      // Добавляем узел в посещенные
      visited[nextMinNode.getKey()] = nextMinNode

      // Добавляем ребра узла в очередь
      nextMinNode.getEdges().forEach((graphEdge) => {
        // Добавляем только те ребра, которые ведут к непосещенным узлам
        if (
          !visited[graphEdge.from.getKey()] ||
          !visited[graphEdge.to.getKey()]
        ) {
          edgesQueue.add(graphEdge, graphEdge.weight)
        }
      })
    }
  }

  return minimumSpanningTree
}

// algorithms/graphs/__tests__/prim.test.js
import GraphNode from '../../../data-structures/graph/node'
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import prim from '../prim'

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

      prim(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 = prim(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('A,B,C,E,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 = prim(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__/prim

❯ Топологическая сортировка

Описание

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

Топологическая сортировка или топологическое упорядочение (topological sort) направленного графа — это линейное упорядочение его вершин, при котором для каждого направленного ребра uv от вершины u до вершины v, u предшествует v в упорядочении.

Например, вершины графа могут представлять задачи, которые необходимо выполнить, а ребра могут представлять ограничения, согласно которым одна задача должна быть выполнена перед другой; в этом приложении топологическое упорядочение — это просто допустимая последовательность задач.

Топологическое упорядочение возможно тогда и только тогда, когда граф не имеет направленных циклов, то есть если он является направленным ациклическим графом (directed acyclic graph, DAG). Любой DAG имеет по крайней мере одно топологическое упорядочение, и существуют алгоритмы линейного времени для его построения.

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

Пример

Приведенный граф может быть упорядочен несколькими способами, в том числе:

• 5, 7, 3, 11, 8, 2, 9, 10 — визуально слева направо, сверху вниз
• 3, 5, 7, 8, 11, 2, 9, 10 — сначала доступная вершина с наименьшим номером
• 5, 7, 3, 8, 11, 10, 9, 2 — сначала доступная вершина с наименьшим количеством ребер
• 7, 5, 11, 3, 10, 8, 9, 2 — сначала доступная вершина с наибольшим номером
• 5, 7, 11, 2, 3, 8, 9, 10 — сверху вниз, слева направо
• 3, 7, 8, 5, 11, 10, 2, 9 — произвольный порядок

Применение

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

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

Реализация

Существует несколько алгоритмов для топологического упорядочения. В нашей реализации будет использоваться такой алгоритм, как поиск в глубину, и такая структура данных, как стек:

// algorithms/graphs/topological-sort.js
import Stack from '../../data-structures/stack'
import depthFirstSearch from './depth-first-search'

// Функция принимает граф
export default function topologicalSort(graph) {
  // Узлы, которые мы хотим посетить
  const unvisited = graph.getAllNodes().reduce((a, c) => {
    a[c.getKey()] = c
    return a
  }, {})

  // Посещенные узлы
  const visited = {}

  // Стек отсортированных узлов
  const stack = new Stack()

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

      // Удаляем узел из непосещенных
      delete unvisited[currentNode.getKey()]
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode }) => {
      // Помещаем полностью исследованный узел в стек
      stack.push(currentNode)
    },
    // Обработчик определения допустимости обхода следующего узла
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход посещенных узлов
      return !visited[nextNode.getKey()]
    },
  }

  // Перебираем непосещенные узлы
  while (Object.keys(unvisited).length) {
    const currentKey = Object.keys(unvisited)[0]
    const currentNode = unvisited[currentKey]

    depthFirstSearch(graph, currentNode, callbacks)
  }

  // Преобразуем стек в массив и возвращаем его
  return stack.toArray()
}

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

// algorithms/graphs/__tests__/topological-sort.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import topologicalSort from '../topological-sort'

describe('topologicalSort', () => {
  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 edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeBD = new GraphEdge(nodeB, nodeD)
    const edgeCE = new GraphEdge(nodeC, nodeE)
    const edgeDF = new GraphEdge(nodeD, nodeF)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeEH = new GraphEdge(nodeE, nodeH)
    const edgeFG = new GraphEdge(nodeF, nodeG)

    const graph = new Graph(true)

    graph
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeBD)
      .addEdge(edgeCE)
      .addEdge(edgeDF)
      .addEdge(edgeEF)
      .addEdge(edgeEH)
      .addEdge(edgeFG)

    const sortedVertices = topologicalSort(graph)

    expect(sortedVertices).toBeDefined()
    expect(sortedVertices.length).toBe(graph.getAllNodes().length)
    expect(sortedVertices).toEqual([
      nodeB,
      nodeD,
      nodeA,
      nodeC,
      nodeE,
      nodeH,
      nodeF,
      nodeG,
    ])
  })
})

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

npm run test ./algorithms/graphs/__tests__/topological-sort

❯ Точка сочленения

Описание

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

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

Каждый цвет представляет компонент связности. Многоцветные вершины — точки сочленения, принадлежащие разным компонентам связности

Вершина графа G называется шарниром, если подграф G1, полученный из графа G удалением вершины v и всех инцидентных ей ребер, состоит из большего количества компонент связности, чем исходный граф G.

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

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

Граф, содержащий два шарнира (вершины 2 и 5) и три блока (1,2, 2,3,4,5, 5,6)

Реализация

Существует несколько алгоритмов для поиска точек сочленения в графе. В нашей реализации мы в очередной раз прибегнем с старому-доброму поиску в глубину:

// algorithms/graphs/articulation-points.js
import depthFirstSearch from './depth-first-search'

// Метаданные узла
class VisitMetadata {
  constructor({ discoveryTime, lowDiscoveryTime }) {
    // Время исследования
    this.discoveryTime = discoveryTime
    // Наименьшее время исследования
    this.lowDiscoveryTime = lowDiscoveryTime
    // Счетчик независимых потомков
    this.independentChildrenCount = 0
  }
}

// Функция принимает граф
export default function articulationPoints(graph) {
  // Посещенные вершины
  const visited = {}

  // Точки сочленения
  const articulationPoints = {}

  // Время, необходимое для исследования текущего узла
  // (измеряется в количестве посещений узлов)
  let discoveryTime = 0

  const startNode = graph.getAllNodes()[0]

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode, previousNode }) => {
      // Увеличиваем время исследования
      discoveryTime += 1

      // Помещаем текущий узел в посещенные
      visited[currentNode.getKey()] = new VisitMetadata({
        discoveryTime,
        lowDiscoveryTime: discoveryTime,
      })

      if (previousNode) {
        // Обновляем счетчик потомков предыдущего узла
        visited[previousNode.getKey()].independentChildrenCount += 1
      }
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode, previousNode }) => {
      if (!previousNode) return

      // Обновляем `lowDiscoveryTime` наименьшим временем соседних узлов
      visited[currentNode.getKey()].lowDiscoveryTime = currentNode
        .getNeighbors()
        .filter((n) => n.getKey() !== previousNode.getKey())
        .reduce((minTime, n) => {
          const lowTime = visited[n.getKey()].lowDiscoveryTime
          return lowTime < minTime ? lowTime : minTime
        }, visited[currentNode.getKey()].lowDiscoveryTime)

      // Определяем, является ли предыдущий узел точкой сочленения.
      // Для этого нужно проверить два условия ИЛИ:
      // 1. Это корневой узел с (минимум) двумя независимыми потомками.
      // 2. Его время исследования <= наименьшее время соседа
      if (previousNode === startNode) {
        // Проверяем, что корневой узел имеет как минимум двух независимых потомков
        if (visited[previousNode.getKey()].independentChildrenCount > 1) {
          articulationPoints[previousNode.getKey()] = previousNode
        }
      } else {
        const currentLDT = visited[currentNode.getKey()].lowDiscoveryTime
        const parentDT = visited[previousNode.getKey()].discoveryTime
        // Проверяем, что время исследования узла <= наименьшее время соседа
        if (parentDT <= currentLDT) {
          articulationPoints[previousNode.getKey()] = previousNode
        }
      }
    },
    // Обработчик определения допустимости исследования узла
    allowTraverse: ({ nextNode }) => {
      // Запрещаем исследование посещенных узлов
      return !visited[nextNode.getKey()]
    },
  }

  // Запускаем поиск в глубину
  depthFirstSearch(graph, startNode, callbacks)

  return articulationPoints
}

// algorithms/graphs/__tests__/articulation-points.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import articulationPoints from '../articulation-points'

describe('articulationPoints', () => {
  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)

    const graph = new Graph()

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

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(2)
    expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())
    expect(articulationPointsSet[1].getKey()).toBe(nodeB.getKey())
  })

  it('должен найти точки сочленения в простом графе с обратным ребром #1', () => {
    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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeAC = new GraphEdge(nodeA, nodeC)

    const graph = new Graph()

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

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(1)
    expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())
  })

  it('должен найти точки сочленения в простом графе с обратным ребром #2', () => {
    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 edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeAE = new GraphEdge(nodeA, nodeE)
    const edgeCE = new GraphEdge(nodeC, nodeE)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeAE)
      .addEdge(edgeCE)
      .addEdge(edgeBC)
      .addEdge(edgeCD)

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(1)
    expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())
  })

  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeGF = new GraphEdge(nodeG, nodeF)
    const edgeFH = new GraphEdge(nodeF, nodeH)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeCD)
      .addEdge(edgeDE)
      .addEdge(edgeEG)
      .addEdge(edgeEF)
      .addEdge(edgeGF)
      .addEdge(edgeFH)

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(4)
    expect(articulationPointsSet[0].getKey()).toBe(nodeF.getKey())
    expect(articulationPointsSet[1].getKey()).toBe(nodeE.getKey())
    expect(articulationPointsSet[2].getKey()).toBe(nodeD.getKey())
    expect(articulationPointsSet[3].getKey()).toBe(nodeC.getKey())
  })

  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeGF = new GraphEdge(nodeG, nodeF)
    const edgeFH = new GraphEdge(nodeF, nodeH)

    const graph = new Graph()

    graph
      .addEdge(edgeDE)
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeCD)
      .addEdge(edgeEG)
      .addEdge(edgeEF)
      .addEdge(edgeGF)
      .addEdge(edgeFH)

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(4)
    expect(articulationPointsSet[0].getKey()).toBe(nodeF.getKey())
    expect(articulationPointsSet[1].getKey()).toBe(nodeE.getKey())
    expect(articulationPointsSet[2].getKey()).toBe(nodeC.getKey())
    expect(articulationPointsSet[3].getKey()).toBe(nodeD.getKey())
  })

  it('должен найти точки сочленения еще в одном графе #1', () => {
    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 edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)

    const graph = new Graph()

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

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(2)
    expect(articulationPointsSet[0].getKey()).toBe(nodeD.getKey())
    expect(articulationPointsSet[1].getKey()).toBe(nodeC.getKey())
  })

  it('должен найти точки сочленения еще в одном графе #2', () => {
    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 edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeCE = new GraphEdge(nodeC, nodeE)
    const edgeCF = new GraphEdge(nodeC, nodeF)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeFG = new GraphEdge(nodeF, nodeG)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeCD)
      .addEdge(edgeCE)
      .addEdge(edgeCF)
      .addEdge(edgeEG)
      .addEdge(edgeFG)

    const articulationPointsSet = Object.values(articulationPoints(graph))

    expect(articulationPointsSet.length).toBe(1)
    expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())
  })
})

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

npm run test ./algorithms/graphs/__tests__/articulation-points

❯ Мост

Описание

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

Мост (bridge) — это ребро, удаление которого увеличивает число компонент связности. Такие ребра также известны как разрезающие ребра (cut-edge), разрезающие дуги (cut arc) или перешейки (isthmus). Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.

Граф с 6 мостами (выделены красным)

Неориентированный связный граф, не имеющий мостов

Деревья и леса

Граф с n вершинами может содержать не более n-1 мостов, поскольку добавление еще одного ребра неминуемо приведет к появлению цикла. Графы, имеющие в точности n-1 мостов, известны как деревья, а графы, в которых любое ребро является мостом — это леса.

Связь с вершинной связностью

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

Реализация

Существует несколько алгоритмов для поиска мостов в графе. В нашей реализации мы в очередной раз прибегнем с старому-доброму поиску в глубину:

// algorithms/graphs/bridges.js
import depthFirstSearch from './depth-first-search'

// Метаданные узла
class VisitMetadata {
  constructor({ discoveryTime, lowDiscoveryTime }) {
    // Время исследования
    this.discoveryTime = discoveryTime
    // Наименьшее время исследования
    this.lowDiscoveryTime = lowDiscoveryTime
  }
}

// Функция принимает граф
export default function graphBridges(graph) {
  // Посещенные узлы
  const visited = {}
  // Мосты
  const bridges = {}

  // Время, необходимое для исследования текущего узла
  // (измеряется в количестве посещений узлов)
  let discoveryTime = 0

  const startNode = graph.getAllNodes()[0]

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode }) => {
      // Увеличиваем время исследования
      discoveryTime += 1

      // Помещаем текущий узел в посещенные
      visited[currentNode.getKey()] = new VisitMetadata({
        discoveryTime,
        lowDiscoveryTime: discoveryTime,
      })
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode, previousNode }) => {
      if (!previousNode) return

      // Обновляем `lowDiscoveryTime` наименьшим временем соседних узлов
      visited[currentNode.getKey()].lowDiscoveryTime = currentNode
        .getNeighbors()
        .filter((n) => n.getKey() !== previousNode.getKey())
        .reduce((minTime, n) => {
          const lowTime = visited[n.getKey()].lowDiscoveryTime
          return lowTime < minTime ? lowTime : minTime
        }, visited[currentNode.getKey()].lowDiscoveryTime)

      // Сравниваем минимальное время исследования.
      // Если текущее время меньше, чем время предыдущего узла,
      // обновляем `lowDiscoveryTime` предыдущего узла
      const currentLDT = visited[currentNode.getKey()].lowDiscoveryTime
      const previousLDT = visited[previousNode.getKey()].lowDiscoveryTime
      if (currentLDT < previousLDT) {
        visited[previousNode.getKey()].lowDiscoveryTime = currentLDT
      }

      // Сравниваем текущее минимальное время исследования со временем предка.
      // Проверяем наличие короткого пути.
      // Если мы не можем добраться до текущего узла иначе, чем через предка,
      // значит, ребро между текущим узлом и его предком является мостом
      const parentLDT = visited[previousNode.getKey()].discoveryTime
      if (parentLDT < currentLDT) {
        const bridge = graph.findEdge(previousNode, currentNode)
        bridges[bridge.getKey()] = bridge
      }
    },
    // Обработчик определения допустимости обхода следующего узла
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход посещенных узлов
      return !visited[nextNode.getKey()]
    },
  }

  // Запускаем поиск в глубину
  depthFirstSearch(graph, startNode, callbacks)

  return bridges
}

// algorithms/graphs/__tests__/bridges.test.js
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import GraphEdge from '../../../data-structures/graph/edge'
import graphBridges from '../bridges'

describe('graphBridges', () => {
  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)

    const graph = new Graph()

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

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(3)
    expect(bridges[0].getKey()).toBe(edgeCD.getKey())
    expect(bridges[1].getKey()).toBe(edgeBC.getKey())
    expect(bridges[2].getKey()).toBe(edgeAB.getKey())
  })

  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeAC = new GraphEdge(nodeA, nodeC)

    const graph = new Graph()

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

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(1)
    expect(bridges[0].getKey()).toBe(edgeCD.getKey())
  })

  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeGF = new GraphEdge(nodeG, nodeF)
    const edgeFH = new GraphEdge(nodeF, nodeH)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeCD)
      .addEdge(edgeDE)
      .addEdge(edgeEG)
      .addEdge(edgeEF)
      .addEdge(edgeGF)
      .addEdge(edgeFH)

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(3)
    expect(bridges[0].getKey()).toBe(edgeFH.getKey())
    expect(bridges[1].getKey()).toBe(edgeDE.getKey())
    expect(bridges[2].getKey()).toBe(edgeCD.getKey())
  })

  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeGF = new GraphEdge(nodeG, nodeF)
    const edgeFH = new GraphEdge(nodeF, nodeH)

    const graph = new Graph()

    graph
      .addEdge(edgeDE)
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeCD)
      .addEdge(edgeEG)
      .addEdge(edgeEF)
      .addEdge(edgeGF)
      .addEdge(edgeFH)

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(3)
    expect(bridges[0].getKey()).toBe(edgeFH.getKey())
    expect(bridges[1].getKey()).toBe(edgeDE.getKey())
    expect(bridges[2].getKey()).toBe(edgeCD.getKey())
  })

  it('должен найти мосты еще в одном графе #1', () => {
    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 edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)

    const graph = new Graph()

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

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(2)
    expect(bridges[0].getKey()).toBe(edgeDE.getKey())
    expect(bridges[1].getKey()).toBe(edgeCD.getKey())
  })

  it('должен найти мосты еще в одном графе #2', () => {
    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 edgeAC = new GraphEdge(nodeA, nodeC)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCD = new GraphEdge(nodeC, nodeD)
    const edgeCE = new GraphEdge(nodeC, nodeE)
    const edgeCF = new GraphEdge(nodeC, nodeF)
    const edgeEG = new GraphEdge(nodeE, nodeG)
    const edgeFG = new GraphEdge(nodeF, nodeG)

    const graph = new Graph()

    graph
      .addEdge(edgeAB)
      .addEdge(edgeAC)
      .addEdge(edgeBC)
      .addEdge(edgeCD)
      .addEdge(edgeCE)
      .addEdge(edgeCF)
      .addEdge(edgeEG)
      .addEdge(edgeFG)

    const bridges = Object.values(graphBridges(graph))

    expect(bridges.length).toBe(1)
    expect(bridges[0].getKey()).toBe(edgeCD.getKey())
  })
})

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

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

❯ Компонента сильной связности

Описание

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

Ориентированный граф называется сильно связным/связанным (strongly connected), если любые две его вершины s и t сильно связаны, то есть если существует ориентированный путь из s в t и одновременно ориентированный путь из t в s.

Компонентами сильной связности графа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности.

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

Любая вершина графа сильно связана сама с собой.

Алгоритмы

Простейший алгоритм решения задачи о поиске сильно связных компонент в ориентированном графе работает следующим образом:

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.
2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
3. Поиск компонент связности такого неориентированного графа дает компоненты сильной связности.

Очевидно, что основное время работы данного алгоритма занимает транзитивное замыкание.

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

Реализация

В нашей реализации будет использоваться такой алгоритм, как поиск в глубину, и такая структура данных, как стек:

// algorithms/graphs/strongly-connected-components.js
import Stack from '../../data-structures/stack'
import depthFirstSearch from './depth-first-search'

// Функция принимает граф.
// Возвращает стек узлов, упорядоченных по времени исследования
function getNodesSortedByDfsFinishTime(graph) {
  // Список посещенных узлов
  const visited = {}

  // Стек узлов по времени исследования (измеряется в количестве посещений узлов).
  // Все узлы в этом стеке отсортированы по времени исследования в порядке убывания.
  // Узел, который был исследован первым, будет находиться внизу стека, а
  // узел, который был исследован последним, будет находиться наверху стека
  const stack = new Stack()

  // Список непосещенных узлов
  const unvisited = graph.getAllNodes().reduce((a, c) => {
    a[c.getKey()] = c
    return a
  }, {})

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode }) => {
      // Добавляем узел в посещенные
      visited[currentNode.getKey()] = currentNode
      // Удаляем узел из непосещенных
      delete unvisited[currentNode.getKey()]
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode }) => {
      // Помещаем полностью исследованный узел в стек
      stack.push(currentNode)
    },
    // Обработчик определения допустимости обхода следующего узла
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход посещенных узлов
      return !visited[nextNode.getKey()]
    },
  }

  // Перебираем непосещенные узлы и обходим их в глубину
  while (Object.keys(unvisited).length) {
    const startKey = Object.keys(unvisited)[0]
    const startNode = unvisited[startKey]
    delete unvisited[startKey]

    depthFirstSearch(graph, startNode, callbacks)
  }

  return stack
}

// Функция принимает граф и стек узлов, упорядоченных по времени исследования.
// Возвращает наборы компонент связности
function getSCCSets(graph, stack) {
  // Наборы компонент связности
  const sets = []
  // Текущий компонент связности
  let set = []
  // Список посещенных узлов
  const visited = {}

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode }) => {
      // Добавляем узел в текущий компонент связности
      set.push(currentNode)
      // Добавляем узел в посещенные
      visited[currentNode.getKey()] = currentNode
    },
    // Обработчик выхода из узла
    leaveNode: ({ previousNode }) => {
      // Если узел является корневым, значит, мы нашли новый компонент связности
      if (!previousNode) {
        // Добавляем текущий компонент связности в наборы
        sets.push(set.slice())
      }
    },
    // Обработчик определения допустимости обхода следующего узла
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход посещенных узлов
      return !visited[nextNode.getKey()]
    },
  }

  // Перебираем стек узлов и обходим их в глубину
  while (!stack.isEmpty()) {
    const node = stack.pop()

    set = []

    if (!visited[node.getKey()]) {
      depthFirstSearch(graph, node, callbacks)
    }
  }

  return sets
}

// Функция принимает граф
export default function stronglyConnectedComponents(graph) {
  // Получаем стек узлов, упорядоченных по времени исследования
  const stack = getNodesSortedByDfsFinishTime(graph)
  // Инвертируем граф
  graph.reverse()
  // Получаем и возвращаем наборы компонент связности
  return getSCCSets(graph, stack)
}

// algorithms/graphs/__tests__/strongly-connected-components.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import stronglyConnectedComponents from '../strongly-connected-components'

describe('stronglyConnectedComponents', () => {
  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)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCA = new GraphEdge(nodeC, nodeA)
    const edgeCD = new GraphEdge(nodeC, nodeD)

    const graph = new Graph(true)

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

    const components = stronglyConnectedComponents(graph)

    expect(components).toBeDefined()
    expect(components.length).toBe(2)

    expect(components[0][0].getKey()).toBe(nodeA.getKey())
    expect(components[0][1].getKey()).toBe(nodeC.getKey())
    expect(components[0][2].getKey()).toBe(nodeB.getKey())

    expect(components[1][0].getKey()).toBe(nodeD.getKey())
  })

  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 nodeI = new GraphNode('I')
    const nodeJ = new GraphNode('J')
    const nodeK = new GraphNode('K')

    const edgeAB = new GraphEdge(nodeA, nodeB)
    const edgeBC = new GraphEdge(nodeB, nodeC)
    const edgeCA = new GraphEdge(nodeC, nodeA)
    const edgeBD = new GraphEdge(nodeB, nodeD)
    const edgeDE = new GraphEdge(nodeD, nodeE)
    const edgeEF = new GraphEdge(nodeE, nodeF)
    const edgeFD = new GraphEdge(nodeF, nodeD)
    const edgeGF = new GraphEdge(nodeG, nodeF)
    const edgeGH = new GraphEdge(nodeG, nodeH)
    const edgeHI = new GraphEdge(nodeH, nodeI)
    const edgeIJ = new GraphEdge(nodeI, nodeJ)
    const edgeJG = new GraphEdge(nodeJ, nodeG)
    const edgeJK = new GraphEdge(nodeJ, nodeK)

    const graph = new Graph(true)

    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeCA)
      .addEdge(edgeBD)
      .addEdge(edgeDE)
      .addEdge(edgeEF)
      .addEdge(edgeFD)
      .addEdge(edgeGF)
      .addEdge(edgeGH)
      .addEdge(edgeHI)
      .addEdge(edgeIJ)
      .addEdge(edgeJG)
      .addEdge(edgeJK)

    const components = stronglyConnectedComponents(graph)

    expect(components).toBeDefined()
    expect(components.length).toBe(4)

    expect(components[0][0].getKey()).toBe(nodeG.getKey())
    expect(components[0][1].getKey()).toBe(nodeJ.getKey())
    expect(components[0][2].getKey()).toBe(nodeI.getKey())
    expect(components[0][3].getKey()).toBe(nodeH.getKey())

    expect(components[1][0].getKey()).toBe(nodeK.getKey())

    expect(components[2][0].getKey()).toBe(nodeA.getKey())
    expect(components[2][1].getKey()).toBe(nodeC.getKey())
    expect(components[2][2].getKey()).toBe(nodeB.getKey())

    expect(components[3][0].getKey()).toBe(nodeD.getKey())
    expect(components[3][1].getKey()).toBe(nodeF.getKey())
    expect(components[3][2].getKey()).toBe(nodeE.getKey())
  })
})

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

npm run test ./algorithms/graphs/__tests__/strongly-connected-components

❯Задача коммивояжера

Описание

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

Задача коммивояжера (travelling salesman problem, TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города ровно по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешевый, совокупный критерий и т.п.) и соответствующие матрицы расстояний, стоимости и т.д. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжера (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжера (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжера. Также существует обобщение задачи, так называемая обобщенная задача коммивояжера.

Решение задачи коммивояжера: черная линия показывает наикратчайший возможный цикл, соединяющий все красные точки

Оптимальный маршрут коммивояжера через 14 крупнейших городов Германии. Указанный маршрут является самым коротким из возможных 43 589 145 600 вариантов

Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем, как и большинство ее частных случаев. Версия "decision problem" (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжера относится к числу трансвычислительных: уже при относительно небольшом числе городов (> 66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Представление в виде графа

Для возможности применения математического аппарата для решения задачи ее следует представить в виде математической модели. Задачу коммивояжера можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а ребра (i, j) между вершинами i и j — пути сообщения между этими городами. Каждому ребру (i, j) можно сопоставить критерий выгодности маршрута c_ij >= 0, который можно понимать как, например, расстояние между городами, время или стоимость поездки.

Гамильтоновым циклом называется маршрут, включающий ровно по одному разу каждую вершину графа.

В целях упрощения задачи и гарантии существования маршрута обычно считается, что модельный граф задачи является полностью связным, то есть, что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными городами не существует сообщения, этого можно достичь путем ввода ребер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет в оптимальный маршрут, если он существует.

Таким образом, решение задачи коммивояжера — это нахождение гамильтонова цикла минимального веса в полном взвешенном графе.

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

Сложность

Поскольку коммивояжер в каждом из городов встает перед выбором следующего города из тех, что он еще не посетил, существует (n-1)! маршрутов для асимметричной и (n-1)!/2 маршрутов для симметричной задачи коммивояжера. Таким образом, размер пространства поиска факториально зависит от количества городов.

Различные варианты задачи коммивояжера (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга, способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.

Также известно, что при условии P !== NP не существует алгоритма, который для некоторого полинома p вычислял бы такие решения задачи коммивояжера, которые отличались бы от оптимального максимум на коэффициент 2^p(n).

На практике поиск строго оптимального маршрута требуется не всегда. Существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность лучшую, чем 1,5 от оптимальной.

Простые методы решения

• полный перебор
• случайный перебор
• жадные алгоритмы
• метод ближайшего соседа
• метод включения ближайшего города
• метод самого дешевого включения
• метод минимального остовного дерева
• метод имитации отжига

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжера — методы эвристические. Большинство эвристических методов находит не самый эффективный маршрут, а приближенное решение. Зачастую востребованы так называемые "any-time-алгоритмы", то есть, постепенно улучшающие некоторое текущее приближенное решение.

Реализация

Мы решим задачу коммивояжера с помощью грубой силы (brute force), т.е. полным перебором всех возможных путей. Это самая простая, но далеко не самая эффективная реализация алгоритма:

// algorithms/graphs/traveling-salesman.js
// Функция принимает начальный узел, все пути
// на данной итерации и текущий путь.
// Возвращает все возможные пути
function findAllPaths(startNode, paths = [], path = []) {
  // Текущий путь
  const currentPath = [...path, startNode]

  // Посещенные узлы
  const visitedNodes = currentPath.reduce((a, n) => {
    const copy = { ...a }
    copy[n.getKey()] = n
    return copy
  }, {})

  // Непосещенные соседи
  const unvisitedNeighbors = startNode
    .getNeighbors()
    .filter((n) => !visitedNodes[n.getKey()])

  // Если непосещенных соседей не осталось,
  // то путь завершен, сохраняем его
  if (!unvisitedNeighbors.length) {
    paths.push(currentPath)
    return paths
  }

  // Перебираем непосещенных соседей
  for (const neighbor of unvisitedNeighbors) {
    // Рекурсивно исследуем их пути
    findAllPaths(neighbor, paths, currentPath)
  }

  return paths
}

// Функция принимает матрицу смежности, индексы узлов и цикл.
// Возвращает вес/стоимость цикла
function getCycleWeight(adjacencyMatrix, nodesIndices, cycle) {
  let weight = 0

  for (let i = 1; i < cycle.length; i++) {
    const fromNode = cycle[i - 1]
    const toNode = cycle[i]
    const fromIndex = nodesIndices[fromNode.getKey()]
    const toIndex = nodesIndices[toNode.getKey()]
    weight += adjacencyMatrix[fromIndex][toIndex]
  }

  return weight
}

// Функция принимает граф
export default function bfTravellingSalesman(graph) {
  const startNode = graph.getAllNodes()[0]

  // Получаем все возможные пути
  const paths = findAllPaths(startNode)

  // Нас интересуют только пути, образующие циклы
  const cycles = paths.filter((p) => {
    const lastNode = p.at(-1)
    const lastNodeNeighbors = lastNode.getNeighbors()

    return lastNodeNeighbors.includes(startNode)
  })

  // Матрица смежности
  const adjacencyMatrix = graph.getAdjacencyMatrix()
  // Индексы узлов
  const nodesIndices = graph.getNodesIndices()
  // Путь коммивояжера
  let salesmanPath = []
  // Минимальный вес пути коммивояжера
  let salesmanPathWeight = null

  // Перебираем циклы
  for (const cycle of cycles) {
    // Вычисляем вес цикла
    const cycleWeight = getCycleWeight(adjacencyMatrix, nodesIndices, cycle)

    // Нас интересует путь с минимальным весом
    if (salesmanPathWeight === null || cycleWeight < salesmanPathWeight) {
      salesmanPath = cycle
      salesmanPathWeight = cycleWeight
    }
  }

  return salesmanPath
}

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

// algorithms/graphs/__tests__/traveling-salesman.test.js
import GraphEdge from '../../../data-structures/graph/edge'
import Graph from '../../../data-structures/graph/index'
import GraphNode from '../../../data-structures/graph/node'
import bfTravellingSalesman from '../traveling-salesman'

describe('bfTravelingSalesman', () => {
  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 edgeBD = new GraphEdge(nodeB, nodeD, 1)
    const edgeDC = new GraphEdge(nodeD, nodeC, 1)
    const edgeCA = new GraphEdge(nodeC, nodeA, 1)

    const edgeBA = new GraphEdge(nodeB, nodeA, 5)
    const edgeDB = new GraphEdge(nodeD, nodeB, 8)
    const edgeCD = new GraphEdge(nodeC, nodeD, 7)
    const edgeAC = new GraphEdge(nodeA, nodeC, 4)
    const edgeAD = new GraphEdge(nodeA, nodeD, 2)
    const edgeDA = new GraphEdge(nodeD, nodeA, 3)
    const edgeBC = new GraphEdge(nodeB, nodeC, 3)
    const edgeCB = new GraphEdge(nodeC, nodeB, 9)

    const graph = new Graph(true)
    graph
      .addEdge(edgeAB)
      .addEdge(edgeBD)
      .addEdge(edgeDC)
      .addEdge(edgeCA)
      .addEdge(edgeBA)
      .addEdge(edgeDB)
      .addEdge(edgeCD)
      .addEdge(edgeAC)
      .addEdge(edgeAD)
      .addEdge(edgeDA)
      .addEdge(edgeBC)
      .addEdge(edgeCB)

    const salesmanPath = bfTravellingSalesman(graph)

    expect(salesmanPath.length).toBe(4)

    expect(salesmanPath[0].getKey()).toEqual(nodeA.getKey())
    expect(salesmanPath[1].getKey()).toEqual(nodeB.getKey())
    expect(salesmanPath[2].getKey()).toEqual(nodeD.getKey())
    expect(salesmanPath[3].getKey()).toEqual(nodeC.getKey())
  })
})

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

npm run test ./algorithms/graphs/__tests__/traveling-salesman

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

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