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

Описание

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

Алгоритм Прима (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