Алгоритм Прима
Алгоритм предназначен для построения минимального остовного дерева графа G. Шаги: 1. Рассчитываются длины всех ребер графа, являющегося моделью исходного описания объекта. 2. Ребра ранжируются в порядке возрастания длины. 3. Из ребер, инцидентных вершинам построенного фрагмента дерева, выбирается ребро, имеющее минимальную длину и не образующего цикла с ребрами, уже включенными в дерево. На первом шаге выбирается ребро минимальной длины. Процесс заканчивается, когда все вершины соединены ребрами.
Общий вид работы алгоритма показан на рисунке слева. На нем использованы следующие условные обозначения: -множество вариантов, содержащих ребро . - множество вариантов, НЕ содержащих ребро .
И так далее.
|