Введение

Метод поиска минимального остовного дерева

В информатике алгоритм Прима — это жадный алгоритм, который находит минимальное остовное дерево для взвешенного неориентированного графа. Это означает, что он находит подмножество ребер, образующее дерево, включающее каждую вершину, при этом общий вес всех ребер в дереве минимизирован. Алгоритм работает, строя это дерево по одной вершине за раз, начиная с произвольной начальной вершины, и на каждом шаге добавляя самое дешевое возможное соединение от дерева к другой вершине. Алгоритм был разработан в 1930 году чешским математиком Войтехом Ярником и позже повторно открыт и опубликован компьютерными учеными Робертом С. Примом в 1957 году и Эдсгером В. Дейкстрой в 1959 году. Поэтому его также иногда называют алгоритмом Ярника, алгоритмом Прима — Ярника, алгоритмом Прима — Дейкстры или алгоритмом DJP. Другие известные алгоритмы для решения этой задачи включают алгоритм Крускала и алгоритм Борувки. Эти алгоритмы находят минимальный остовный лес в, возможно, несвязном графе; в отличие от этого, наиболее простая форма алгоритма Прима находит только минимальные остовные деревья в связных графах. Однако, запуская алгоритм Прима отдельно для каждой связной компоненты графа, его также можно использовать для поиска минимального остовного леса. С точки зрения асимптотической временной сложности, эти три алгоритма одинаково эффективны для разреженных графов, но медленнее, чем другие более сложные алгоритмы.

Доказательство правильности

Пусть P — связный, взвешенный граф. На каждой итерации алгоритма Прима необходимо найти ребро, соединяющее вершину в подграфе с вершиной вне подграфа. Поскольку P связен, всегда существует путь к каждой вершине. Результат Y алгоритма Прима является деревом, поскольку добавляемые ребра и вершины соединены. Пусть Y1 — минимальное остовное дерево графа P. Если Y1 = Y, то Y является минимальным остовным деревом. В противном случае, пусть e — первое ребро, добавленное при построении дерева Y, которое отсутствует в дереве Y1, а V — множество вершин, соединенных ребрами, добавленными до ребра e. Тогда один конец ребра e находится в множестве V, а другой — нет. Поскольку дерево Y1 является остовным деревом графа P, в дереве Y1 существует путь, соединяющий оба конца ребра e. При движении по этому пути необходимо встретить ребро f, соединяющее вершину в множестве V с вершиной, не входящей в множество V. Теперь, на итерации, когда ребро e было добавлено к дереву Y, ребро f также могло быть добавлено, и оно было бы добавлено вместо ребра e, если бы его вес был меньше веса e. Поскольку ребро f не было добавлено, мы заключаем, что пусть дерево Y2 будет графом, полученным удалением ребра f из дерева Y1 и добавлением ребра e к дереву Y1. Легко показать, что дерево Y2 связно, имеет такое же количество ребер, как дерево Y1, и общий вес его ребер не превышает вес ребер дерева Y1, следовательно, оно также является минимальным остовным деревом графа P и содержит ребро e и все ребра, добавленные до него при построении множества V. Повторяя описанные шаги, мы в конечном итоге получим минимальное остовное дерево графа P, идентичное дереву Y. Это доказывает, что Y является минимальным остовным деревом. Минимальное остовное дерево позволяет первой подвыборке подрегиона быть расширенной до меньшей подвыборки X, которую мы считаем минимальной.

Параллельный алгоритм

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