Графы. Алгоритм Прима

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

Чтобы понять что такое ребро, вес смотрим рисунок
Граф
Вершины графа на этом рисунке обозначены кружками.
Номер вершины — цифра в кружке.
Ребро — отрезок, соединяющий вершины
Вес ребра — синяя цифра над отрезком.

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

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

  • На рисунке изображено мысленное дополнение неполного графа до полного.

Граф
Чтобы искать максимальную оценку маршрута, нужно взять минимальное значение, т.е. это будет (минус Бесконечность), но я буду опсиывать алогритм для минимальной оценки.

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

Созданная матрица смежности для нарисованного графа

∞      10      ∞      ∞
10     ∞       9      20
∞      9        ∞      15
∞      20      15     ∞

В дальнейшем под бесконечностью будет число, которое компилятор воспринимает как максимальное.

На разных машиеах int может иметь разный размер, поэтому на одном ПК может быть один максимум, на другом другой, но это к сведению, а к теме не относится.

А к теме относиться понимание алгоритма Прима. Если вы его понимаете — то это просто великолепно и значит своими силами вполне способны написать программу для его выполнения, если же не понимаете, то придется помучаться и понять теорию.

Для лучшего понимания этой статьи хорошо бы знать, что такое остовное дерево Минимальное остовное дерево
Вот замечательно показанные примеры теоритического выполнения некоторых алгоритмов на графах. Среди этих примеров есть пример работы алгоритма Прима Минимальные остовные деревья
Если кому-то покажется, что этого мало, то вот мое личное художество, анимированный рисунок, только немного не того графа, который я описывал выше. Я посчитал, что тот граф не очень подходит для иллюстрации расчетов, поэтому немного изменил веса ребер.

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

А вот пример реализации алгоритма Прима, правда пример не мой, поэтому я особо его не смогу прокомментировать. Но, несмотря на это, этот пример не должен быть очень сложным для его понимания.

Пример работы

Алгоритм Прима Алгоритм Прима
Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

12 комментариев: Графы. Алгоритм Прима

  • Евгений говорит:

    Почему матрица смежности первого рисунка, вершина 2-2 бесконечность? Нельзя из 2 в 2 попасть по пути 2->4->3->2? И будет сумма веса рёбер, которую мы запишем в матрицу смежности.

    • Арсений говорит:

      Потому что прямого пути из 2 в 2 нет. Матрица инцидентности подразумевает под собой написание именно прямых путей.

  • Фелагунд говорит:

    Условие if(visited[i]!=0) во вложенном цикле при поиске ребра с наименьшим весом лучше переместить во внешний цикл сразу после for(i=1,min=999;i<=n;i++)

    Гораздо оптимальней

  • Карим говорит:

    в коде есть недароботки, например вы не определяете возможно ли вообще соединить все вершины или нет

  • Михаил говорит:

    У меня выдает ошибку «С2872 неоднозначный символ min». Если изменить имя переменной, то я не знаю, где какую вставить… Что посоветуете?

    • admin говорит:

      Заменить все min на min_

      Это произошло, потому что в STL есть функция min, которая сравнивает два значения и возвращает наименьшее. А в коде использована одноимённая переменная. Компилятор поэтому не врубился. В этих случаях просто меняются имена переменных.

      • Михаил говорит:

        действительно! Но теперь не могу понять, почему была проблема. Можете объяснить? И почему «_» все решило?

  • Михаил говорит:

    Все. Сам разобрался, почему так было ) Спасибо за помощь! Давно на этом сайте занимаюсь.

  • Илья говорит:

    Сколько максимально вершин можно вбить?

  • Аноним говорит:

    не правильно выводит для теста:

    4

    0 1 0 0

    0 0 2 0

    0 0 0 5

    4 0 0 0

    выводит 8, а должен 7

    не все варианты смотрит

  • Shel говорит:

    Может быть потому что у вас не матрица смежности, не?))

Добавить комментарий

Ваш e-mail не будет опубликован.

Поиск

 
     
Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

В зоопаpке pебенок, возбужденно тыча пальцем на клетку с пpиматами, кpичит: - Мама ! Мама ! Смотpи - пpогpаммисты ! - Почему ты так pешил ? - Они как папа ! - не мытые, лохматые и мозоли на попе !!

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок