Алгоритм Прима похож на алгоритм Крускала. Это жадный алгоритм, который находит MST (минимальное остовное дерево) для взвешенного неориентированного графа. Начиная с произвольной вершины, алгоритм строит MST по одной вершине за раз, где каждая вершина берет кратчайший путь от корневого узла. Перейдем к нашему примеру.
Хотя мы можем начать с любой вершины, для этого примера мы выберем вершину A. Вершина A имеет прямые ребра к B и I. Стоимость вершины B равна 7, а стоимость вершины I равна 15. Поскольку алгоритм Прима является жадным алгоритмом, он выбирает ребро с наименьшим весом, которым в данном случае является ребро AB. . Цифры зеленого цвета представляют порядок обнаружения вершин.
Вершины A и B теперь могут видеть вершины C и I. Вершина B имеет доступ к C, а вершина A имеет доступ к I. Если смотреть на вершину C, расстояние от B до C равно 5; расстояние от A до I равно 15. Алгоритм Prim выбирает наименьшее ребро, которое в данном случае находится от B-C.
Алгоритм должен учитывать все ребра, которые видны со всех уже обнаруженных вершин. Теперь неоткрытые видимые края - это A-I, C-E, C-D и C-G. Сравнивая веса каждого ребра, алгоритм Прима приходит к выводу, что наименьший вес идет от вершины C к вершине E, поэтому он выбирает это ребро.
Теперь у алгоритма есть доступ к ребрам A-I, C-D, C-G и E-D. Edge E-D имеет самую низкую стоимость, поэтому алгоритм выбирает его следующим.
Алгоритм Прима теперь должен учитывать следующие ребра: A-I, C-G и D-F. Ребро C-D не рассматривается, так как обе вершины уже найдены. Если выбрано это ребро, будет создан цикл. Ребро C-G содержит наименьший вес, поэтому выбирается следующим.
Остались три неоткрытые вершины. Алгоритм Прима выберет наименее затратное ребро из следующего: A-I, D-F, G-F и G-I. Ребро G-F содержит наименее затратное ребро, поэтому оно выбирается следующим.
Прим смотрит на края A-I, F-H и G-I. Поскольку G-I - это наименьшее преимущество, Прим выбирает его следующим.
Наконец, к вершине H можно получить доступ через ребро F-H или ребро I-H. Поскольку край I-H меньше, алгоритм Прима выбирает его.
Поскольку все вершины найдены, алгоритм заканчивается. Найдено минимальное остовное дерево. Порядок обнаружения вершин следующий:
A, B, C, E, D, G, F, I, H.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает этот алгоритм и многое другое.
