Теория и практика параллельных вычислений

         

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


Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть VT есть множество вершин, уже включенных алгоритмом в МОД, а величины di, 1in, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества VT, т.е.

(если для какой-либо вершины iVT не существует ни одной дуги в VT, значение di устанавливается равным ?). В начале работы алгоритма выбирается корневая вершина МОД s и полагается VT={s}, ds=0.

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

  • определяются значения величин di для всех вершин, еще не включенных в состав МОД;
  • выбирается вершина t графа G, имеющая дугу минимального веса до множества VTt:dt, iVT;
  • вершина t включается в VT.

После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения

Трудоемкость нахождения МОД характеризуется квадратичной зависимостью от числа вершин графа T1~n2.



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий