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

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

Основы теории графов: Понятия, необходимые для понимания МОД

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

Что такое граф? Вершины, ребра, взвешенные графы

В самом общем смысле, граф G – это математическая структура, состоящая из двух ключевых элементов: множества вершин (или узлов, точек), обозначаемого как X, и множества ребер (или линий, связей), обозначаемого как U. Таким образом, граф можно формально представить как пару G = (X, U). Вершины X представляют собой объекты, а ребра U – связи между ними.

Если порядок, в котором перечислены вершины, соединенные ребром, не имеет значения (например, дорога из города A в город B такая же, как из B в A), такое ребро называется неориентированным. Соответственно, сам граф, содержащий только такие ребра, называется неориентированным графом. В отличие от него, в ориентированном графе (или орграфе) связи называются дугами, и порядок вершин в паре имеет значение (например, одностороннее движение). В контексте алгоритма Прима мы будем работать исключительно с неориентированными графами.

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

Остовные деревья и их свойства

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

Что означает «является деревом»? Дерево в теории графов – это связный граф, не содержащий циклов. Цикл — это путь, который начинается и заканчивается в одной и той же вершине. Таким образом, остовное дерево — это минимальный связный подграф, включающий все вершины, без избыточных связей, которые могли бы образовывать циклы.

Формально, остовным подграфом графа G=(X,U) называется граф (X, U_p), для которого U_p ⊂ U. Это означает, что остовный подграф имеет то же самое множество вершин, что и исходный граф G, но множество его ребер U_p является подмножеством ребер исходного графа U. Остовное дерево, как отмечалось, является особым случаем остовного подграфа, который не только включает все вершины, но и обладает структурой дерева.

Одно из фундаментальных свойств любого остовного дерева связного графа с N вершинами заключается в том, что оно обязательно содержит N-1 ребро. Это свойство является прямым следствием отсутствия циклов и связности: чтобы соединить N вершин без циклов, требуется ровно N-1 ребро. Это интуитивно понятно: первая вершина не требует ребер, вторая требует одно ребро для соединения с первой, третья — одно для соединения с уже существующей частью дерева, и так далее. И что из этого следует? Такое минимальное количество ребер гарантирует максимальную эффективность с точки зрения ресурсов, ведь каждая добавленная связь является строго необходимой.

Минимальное остовное дерево (МОД): Определение и значение

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

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

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

Алгоритм Прима: Принципы работы и теоретические основы

Алгоритм Прима – один из наиболее элегантных и эффективных методов для нахождения минимального остовного дерева. Он относится к категории «жадных» алгоритмов, что означает принятие локально оптимального решения на каждом шаге в надежде на достижение глобального оптимума.

«Жадный» подход и лемма о безопасном ребре

Сердцевиной алгоритма Прима является его «жадный» подход. На каждой итерации алгоритм выбирает наиболее дешевое (с минимальным весом) ребро, которое соединяет уже построенную часть минимального остовного дерева с вершиной, которая еще не включена в него. Постепенно, ребро за ребром, алгоритм «выращивает» остовное дерево, начиная с одной произвольной вершины.

Корректность такого «жадного» выбора гарантируется фундаментальным принципом, известным как лемма о безопасном ребре. Эта лемма гласит:

Пусть G = (X, U) — связный, взвешенный, неориентированный граф. Пусть A — любое подмножество ребер минимального остовного дерева G. Пусть (U, W) — произвольный разрез графа G, который не пересекается ни одним ребром из A (то есть A не содержит ребер, соединяющих U и W). Если e = (x, y) — ребро минимального веса, пересекающее разрез (U, W), то e является безопасным ребром для A, то есть e может быть добавлено к A, и A ∪ {e} будет частью некоторого минимального остовного дерева.

Проще говоря, если мы разделим вершины графа на два множества – те, что уже входят в формирующийся остов (U), и те, что еще не вошли (W) – то ребро с минимальным весом, которое соединяет вершину из U с вершиной из W, гарантированно будет частью какого-либо минимального остовного дерева. Это дает нам право на каждом шаге жадно выбирать такое ребро, будучи уверенными, что этот выбор не приведет к неоптимальному решению. Что из этого следует? Мы можем доверять каждому шагу алгоритма, зная, что он последовательно строит оптимальное решение.

Сравнение алгоритмов Прима и Дейкстры: Ключевые различия

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

Характеристика	Алгоритм Прима	Алгоритм Дейкстры
Цель	Построение Минимального Остовного Дерева (МОД)	Нахождение кратчайших путей от одной вершины до всех остальных
Критерий выбора	Минимизация веса ребра, соединяющего текущий остов с новой вершиной	Минимизация суммы весов вдоль пути от начальной вершины до текущей
Расширение	Расширяет связный остов, добавляя ребра к его периметру	Расширяет множество вершин, для которых найден кратчайший путь
Типы графов	Только неориентированные связные графы	Ориентированные и неориентированные графы
Отрицательные веса	Может корректно работать с отрицательными весами ребер для МОД	Не может корректно работать с отрицательными весами ребер (может зацикливаться или давать неверные результаты)
Результат	Одно дерево, связывающее все вершины, с минимальной общей стоимостью	Набор кратчайших путей от источника до каждой достижимой вершины

Детализация различий:

• Назначение: Алгоритм Прима строит единое дерево, которое связывает все вершины графа с минимальной суммарной стоимостью ребер. Алгоритм Дейкстры ищет набор путей, каждый из которых является кратчайшим от заданной начальной вершины до каждой другой вершины.
• Выбор ребра/вершины: Прим всегда выбирает ребро, которое напрямую соединяет уже сформированную часть остова с ещё не включённой вершиной, причём это ребро должно быть минимальным среди всех таких «пограничных» рёбер. Дейкстра же выбирает вершину, до которой найден наикратчайший путь от старта на текущий момент.
• Тип графа: Алгоритм Прима по своей природе работает с неориентированными графами, так как концепция остовного дерева подразумевает двунаправленные связи. Дейкстра более гибок и применим к ориентированным графам.
• Отрицательные веса: Это критическое различие. Алгоритм Прима может корректно находить МОД в графах с отрицательными весами ребер (при условии, что граф связный), так как его «жадность» основана на локальном минимуме ребра, а не на сумме путей. Алгоритм Дейкстры, напротив, не гарантирует корректности, если в графе есть отрицательные веса, поскольку он может неверно обрабатывать уже «финализированные» кратчайшие пути при появлении более коротких альтернатив через отрицательные ребра. Для графов с отрицательными весами для кратчайших путей используются другие алгоритмы, например, Беллмана-Форда.

Таким образом, несмотря на внешнее сходство в использовании «жадного» подхода, Прим и Дейкстра служат разным целям и имеют разные области применимости.

Пошаговая процедура применения алгоритма Прима

Для успешного применения алгоритма Прима, особенно в контексте контрольной работы, важно понимать каждый шаг процесса. Мы будем использовать два множества вершин: U (вершины, уже включенные в остов) и W (вершины, еще не включенные в остов).

Инициализация алгоритма: Выбор начальной вершины

1. Выбор начальной вершины: Алгоритм Прима начинается с произвольной вершины графа. Выбор стартовой вершины не влияет на итоговый вес минимального остовного дерева. Это одно из важных свойств алгоритма.

• Допустим, мы выбираем вершину ‘A’ как начальную.
• Множество U (вершины в остове) инициализируется этой вершиной: U = {‘A’}.
• Множество W (вершины вне остова) инициализируется всеми остальными вершинами графа: W = {все вершины графа} — {‘A’}.
• Список ребер формирующегося МОД (обозначим его как МОД_ребра) изначально пуст.

Итерационный процесс: Выбор и добавление «безопасного» ребра

2. Итерации (пока W непусто): На каждой итерации алгоритм ищет «безопасное» ребро для добавления в МОД.

• Поиск ребра: Найти ребро e = (x, y) наименьшего веса среди всех ребер, которые удовлетворяют двум условиям:
  • Вершина x принадлежит множеству U (уже в остове).
  • Вершина y принадлежит множеству W (еще не в остове).
• Это ребро является «безопасным» согласно лемме о безопасном ребре. Если таких ребер несколько (с одинаковым минимальным весом), можно выбрать любое из них.
• Добавление: Добавить найденное ребро e к МОД_ребра.
• Обновление множеств: Перенести вершину y (которая только что была соединена с остовом) из множества W в множество U.

Этот процесс повторяется до тех пор, пока множество W не станет пустым.

Завершение алгоритма: Построение МОД

3. Завершение: Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа, то есть пока множество W не станет пустым. В этот момент МОД_ребра будет содержать N-1 ребро (где N — количество вершин), образующих минимальное остовное дерево. Сумма весов этих ребер будет минимальной возможной.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

Пример применения алгоритма Прима с детализацией каждого шага и порядка включения ребер

Рассмотрим следующий взвешенный неориентированный граф:

Граф:
Вершины: A, B, C, D, E, F
Ребра и их веса:
(A, B): 4
(A, C): 2
(B, C): 5
(B, D): 10
(C, D): 8
(C, E): 3
(D, E): 7
(D, F): 6
(E, F): 1

Задача: Построить минимальное остовное дерево, начиная с вершины A, и указать порядок включения ребер.

Шаг 0: Инициализация

• Начальная вершина: A
• U = {A}
• W = {B, C, D, E, F}
• МОД_ребра = {}
• Общий вес МОД = 0

Шаг 1:

• Ребра, соединяющие U с W:
  • (A, B) с весом 4
  • (A, C) с весом 2
• Выбор: Ребро (A, C) имеет минимальный вес (2).
• Действие: Добавляем (A, C) в МОД_ребра.
• Обновление: U = {A, C}, W = {B, D, E, F}
• МОД_ребра = {(A, C)}
• Общий вес МОД = 2
• Порядок включения ребер: (A, C)

Шаг 2:

• Ребра, соединяющие U с W:
  • Из A: (A, B) с весом 4
  • Из C: (C, B) с весом 5
  • Из C: (C, D) с весом 8
  • Из C: (C, E) с весом 3
• Выбор: Ребро (C, E) имеет минимальный вес (3). (A, B) тоже кандидат, но (C, E) меньше.
• Действие: Добавляем (C, E) в МОД_ребра.
• Обновление: U = {A, C, E}, W = {B, D, F}
• МОД_ребра = {(A, C), (C, E)}
• Общий вес МОД = 2 + 3 = 5
• Порядок включения ребер: (A, C), (C, E)

Шаг 3:

• Ребра, соединяющие U с W:
  • Из A: (A, B) с весом 4
  • Из C: (C, B) с весом 5, (C, D) с весом 8
  • Из E: (E, D) с весом 7, (E, F) с весом 1
• Выбор: Ребро (E, F) имеет минимальный вес (1).
• Действие: Добавляем (E, F) в МОД_ребра.
• Обновление: U = {A, C, E, F}, W = {B, D}
• МОД_ребра = {(A, C), (C, E), (E, F)}
• Общий вес МОД = 5 + 1 = 6
• Порядок включения ребер: (A, C), (C, E), (E, F)

Шаг 4:

• Ребра, соединяющие U с W:
  • Из A: (A, B) с весом 4
  • Из C: (C, B) с весом 5, (C, D) с весом 8
  • Из E: (E, D) с весом 7
  • Из F: (F, D) с весом 6
• Выбор: Ребро (A, B) имеет минимальный вес (4).
• Действие: Добавляем (A, B) в МОД_ребра.
• Обновление: U = {A, C, E, F, B}, W = {D}
• МОД_ребра = {(A, C), (C, E), (E, F), (A, B)}
• Общий вес МОД = 6 + 4 = 10
• Порядок включения ребер: (A, C), (C, E), (E, F), (A, B)

Шаг 5:

• Ребра, соединяющие U с W:
  • Из B: (B, D) с весом 10
  • Из C: (C, D) с весом 8
  • Из E: (E, D) с весом 7
  • Из F: (F, D) с весом 6
• Выбор: Ребро (F, D) имеет минимальный вес (6).
• Действие: Добавляем (F, D) в МОД_ребра.
• Обновление: U = {A, C, E, F, B, D}, W = {}
• МОД_ребра = {(A, C), (C, E), (E, F), (A, B), (F, D)}
• Общий вес МОД = 10 + 6 = 16
• Порядок включения ребер: (A, C), (C, E), (E, F), (A, B), (F, D)

Завершение: Множество W пусто. Все вершины включены в остов.

Итоговое МОД: Ребра {(A, C), (C, E), (E, F), (A, B), (F, D)} с общим весом 16.
Порядок включения ребер:

1. (A, C) [вес 2]
2. (C, E) [вес 3]
3. (E, F) [вес 1]
4. (A, B) [вес 4]
5. (F, D) [вес 6]

Особенности реализации и применимость алгоритма Прима

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

Обработка циклов: Принципиальное отсутствие в алгоритме Прима

Одной из ключевых характеристик остовного дерева является отсутствие циклов. В этом отношении алгоритм Прима демонстрирует свое превосходство: он по своей природе не допускает образования циклов.

Почему это так? На каждом шаге алгоритм Прима добавляет ребро, которое соединяет уже существующую, связную часть формирующегося остова (множество U) с новой вершиной, которая до этого момента не входила в этот остов (множество W). То есть, каждое добавляемое ребро всегда соединяет два различных компонента: один – уже сформированное дерево, другой – отдельную вершину. Таким образом, добавление такого ребра всегда увеличивает размер дерева, не создавая при этом петли или цикла внутри уже связной части. Новая вершина y из W всегда «прикрепляется» к одной из вершин x из U с помощью ребра (x, y), обеспечивая связность без замыкания цепи. Что из этого следует? Надежность алгоритма Прима в построении корректного дерева без циклов является его неотъемлемым свойством, упрощающим его применение.

Если бы алгоритм мог добавить ребро, соединяющее две вершины из множества U, это привело бы к образованию цикла. Но это противоречит логике алгоритма, так как он всегда ищет ребро, пересекающее «разрез» между U и W.

Анализ сложности алгоритма Прима: От матрицы смежности до фибоначчиевой кучи

Эффективность любого алгоритма измеряется его временной сложностью – тем, как быстро время выполнения увеличивается с ростом размера входных данных. Сложность алгоритма Прима сильно зависит от того, как реализована приоритетная очередь для выбора следующего «безопасного» ребра.

1. Реализация с использованием матрицы смежности:
   • Представление графа: Граф представлен матрицей смежности размером N x N, где N – число вершин. adjacency_matrix[i][j] хранит вес ребра между вершинами i и j.
   • Поиск ребра: На каждой из N-1 итераций алгоритму необходимо просмотреть все вершины в W и для каждой из них – все ребра, соединяющие её с вершинами в U. В худшем случае это означает просмотр до N вершин и N ребер для каждой.
   • Сложность: O(N²). Эта реализация наиболее эффективна для плотных графов, где количество ребер M ≈ N². В этом случае, M log N может быть больше N².
2. Реализация с использованием списка смежности и двоичной (бинарной) кучи (приоритетной очереди):
   • Представление графа: Граф представлен списком смежности, где для каждой вершины хранится список её соседей и весов соответствующих ребер.
   • Приоритетная очередь: Двоичная куча используется для хранения потенциальных «безопасных» ребер, отсортированных по весу. На каждой итерации из кучи извлекается ребро с минимальным весом. Когда новая вершина y добавляется в U, все её смежные ребра, ведущие в W, добавляются в кучу (или обновляются, если уже присутствуют).
   • Сложность: O(M log N), где M – число ребер, N – число вершин.
     • Извлечение минимального элемента из кучи: O(log N).
     • Обновление/добавление ребер в кучу: O(log N) для каждого ребра. В худшем случае, когда вершина y имеет степень deg(y), происходит deg(y) операций. Сумма степеней всех вершин равна 2M.
     • Итого: N-1 итераций, M операций на кучу.
     • Эта реализация более эффективна для разреженных графов, где M значительно меньше N².
3. Реализация с использованием фибоначчиевой кучи:
   • Приоритетная очередь: Фибоначчиева куча – это более сложная структура данных, которая позволяет достичь амортизированной временной сложности O(1) для операции уменьшения ключа (decrease-key) и O(log N) для извлечения минимума.
   • Сложность: O(M + N log N).
     • N операций извлечения минимума: O(N log N).
     • M операций уменьшения ключа: O(M) амортизированно.
     • Эта реализация является теоретически самой быстрой, но из-за высокой константы в реальных условиях редко превосходит двоичную кучу для практических задач, кроме очень больших графов. Тем не менее, она демонстрирует пределы оптимизации алгоритма.

Структура данных для очереди приоритетов	Временная сложность	Описание
Матрица смежности (без кучи)	O(N2)	Простой, эффективен для плотных графов
Список смежности + Двоичная куча	O(M log N)	Универсальный, эффективен для разреженных графов
Список смежности + Фибоначчиева куча	O(M + N log N)	Теоретически наиболее эффективный, но сложен в реализации

Практические области применения МОД и алгоритма Прима

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

• Проектирование коммуникационных сетей: Одна из классических задач. Представьте, что необходимо соединить несколько географически разрозненных населенных пунктов телефонными линиями, оптоволоконными кабелями или радиорелейными станциями. Каждое возможное соединение имеет свою стоимость (длина кабеля, стоимость прокладки). Алгоритм Прима позволяет найти оптимальную конфигурацию сети, которая связывает все точки с минимальными общими затратами.
• Проектирование электрических сетей: Аналогично коммуникационным сетям, при прокладке линий электропередач между подстанциями или потребителями, МОД помогает минимизировать затраты на кабели и монтаж, обеспечивая при этом полную связность. Алгоритм может использоваться для составления полной системы уравнений для токов и напряжений, основываясь на минимальной топологии сети.
• Транспортная логистика: Задача определения оптимальных маршрутов для доставки грузов, где необходимо соединить все склады или точки доставки с минимальной суммарной длиной пути.
• Евклидова задача о минимальном остове: Если даны N точек на плоскости (например, координаты городов), и требуется найти остов минимального веса, соединяющий их все. Вес ребра в этом случае – это евклидово расстояние между точками.
• Кластерный анализ: В некоторых методах кластеризации МОД используется для выявления групп близко расположенных объектов, где «ребра» представляют собой меры сходства или расстояния.
• Компьютерное зрение и обработка изображений: МОД может использоваться для сегментации изображений, где пиксели рассматриваются как вершины графа, а веса ребер отражают различие между соседними пикселями.
• Биоинформатика: Анализ связей между генами, белками или другими биологическими объектами.

Заключение: Резюме и дальнейшие перспективы

Мы совершили погружение в мир теории графов, детально рассмотрев один из её краеугольных камней – алгоритм Прима для построения Минимального Остовного Дерева (МОД). От фундаментальных определений графа, вершины, ребра и их весов, до тонкостей остовных деревьев и их ключевого свойства (N-1 ребро для N вершин), мы выстроили прочную теоретическую базу.

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

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

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

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

Список использованной литературы

1. Алгоритм Прима. DISCOPAL. URL: discopal.ru (дата обращения: 03.11.2025).
2. Остовные деревья: определения, лемма о безопасном ребре. Викиконспекты. URL: neerc.ifmo.ru (дата обращения: 03.11.2025).
3. Графов теория. Большая российская энциклопедия — электронная версия. URL: bigenc.ru (дата обращения: 03.11.2025).
4. Остовное дерево. Algocode wiki. URL: algocode.ru (дата обращения: 03.11.2025).
5. Поиск Минимального Остовного дерева. Вики справка Graph Online. URL: graphonline.ru (дата обращения: 03.11.2025).
6. Минимальное остовное дерево. WikiGrapp. URL: pco.iis.nsk.su (дата обращения: 03.11.2025).
7. Алгоритм Прима. EVILEG. URL: evileg.ru (дата обращения: 03.11.2025).
8. Алгоритм Прима. Алгоритмика. URL: algorithmica.org (дата обращения: 03.11.2025).
9. Алгоритм Прима. elibrary.sgu.ru. URL: elibrary.sgu.ru (дата обращения: 03.11.2025).
10. Алгоритм Прима. ЦСТ. URL: cst.ru (дата обращения: 03.11.2025).
11. Алгоритм Прима для остовного дерева / Али Алиев. ali-aliev.ru. URL: ali-aliev.ru (дата обращения: 03.11.2025).
12. Остовное дерево. bgtu.by. URL: bgtu.by (дата обращения: 03.11.2025).
13. Дискретная математика. Теория графов. Рязанский государственный радиотехнический университет. URL: rgrtu.ru (дата обращения: 03.11.2025).
14. Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала. brestprog. URL: brestprog.by (дата обращения: 03.11.2025).
15. Минимальное остовное дерево. Алгоритм Прима. e-maxx.ru. URL: e-maxx.ru (дата обращения: 03.11.2025).
16. Алгоритм Прима. AlgoWiki. URL: algowiki-project.org (дата обращения: 03.11.2025).
17. Дискретная математика. Лекция 12. МЭИ. URL: mpei.ru (дата обращения: 03.11.2025).
18. Алгоритм Прима. Хабр. URL: habr.com (дата обращения: 03.11.2025).
19. Связность и остовные деревья. Алгоритмика. URL: algorithmica.org (дата обращения: 03.11.2025).
20. Алгоритм Краскала, Прима для нахождения минимального остовного дерева. Habr. URL: habr.com (дата обращения: 03.11.2025).