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). Начальные значения элементов массива равны номерам соответствующих вершин
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz