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

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

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

Вход: Связный неориентированный граф

Выход: Множество T рёбер минимального остовного дерева

while (V-U не пусто)

{ Выбрать ребро (u, v) наименьшей стоимости,

u из U, v из V-U;

Добавить v к U (и убрать из V-U); }

Временная сложность алгоритма Прима есть O( ).

Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами. В качестве начальной произвольно выбирается вершина D. Каждая из вершин A, B, E and F соединина с D единственным ребром. Вершина A — ближайшая к D, и выбирается как вторая вершина вместе с ребром AD. Выбраны все вершины, минимальное остовное дерево построено (выделено зеленым). В этом случае его вес равен 39.
Алгоритм Форда - Фалкерсона

решает задачу нахождения максимального потока в транспортной сети.