end; end; {*Solve*} 3.3.3.
end;
end; {*Solve*}
3.3.3. Каркас минимального веса. Метод Краскала
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается перечнем ребер с указанием их веса. Массив P (array[1..3,1..N*(N-1) div 2] of integer). Результат. Каркас с минимальным суммарным весом Q=<V,T>, где T?E.
Пример. Граф и процесс построения каркаса по методу Краскала.
Шаг 1. Начать с вполне несвязного графа G, содержащего N вершин.
Шаг 2. Упорядочить ребра графа G в порядке неубывания их весов.
Шаг 3. Начав с первого ребра в этом перечне, добавлять ребра в графе Q, соблюдая условие: добавление не должно приводить к появлению цикла в Q.
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса.
Какие структуры данных требуются для реализации шага 3? Введем массив меток вершин графа (Mark:array[1..N] of integer). Начальные значения элементов массива равны номерам соответствующих вершин
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
