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

Описание

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

Алгоритм Краскала (или Крускала, 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