СибГУТИ Лабораторная работа 1 Вариант 8 Теория сложности вычислительных процессов и структур скачать бесплатно

Задание

Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.

Вывести ребра остова минимального веса в порядке их присоединения и вес остова.

Номер варианта выбирается по последней цифре пароля.

Вариант 8

0 14 9 3 22 17 16 0 14 18

14 0 19 0 2 0 11 14 21 20

9 19 0 17 20 22 4 4 8 9

3 0 17 0 11 3 20 12 10 15

22 2 20 11 0 14 19 17 15 19

17 0 22 3 14 0 0 6 10 0

16 11 4 20 19 0 0 3 11 9

0 14 4 12 17 6 3 0 7 4

14 21 8 10 15 10 11 7 0 7

18 20 9 15 19 0 9 4 7 0

Описание алгоритма Краскала

Задача: Дан граф G=(V,E) – связный, неориентированный, взвешенный. Нам нужно выделить в нем минимальный (по суммарному весу ребер) связный граф с теми же вершинами – остов (остовное дерево), т.е. исключить из графа часть ребер таким образом, чтобы сумма весов оставшихся была минимальна, и получившийся граф по- прежнему был связным.

Идея решения: Для решения этой задачи обычно применяется алгоритм Краскала (классический пример т.н. “жадного алгоритма”).

Алгоритм Краскала:

1. Сначала упорядочиваем все ребра по возрастанию весов.

2. Заводим таблицу: в левой колонке список ребер, в правой компоненты связности.

3. В первой строчке список ребер пустой и все компоненты связности одновершинные. Берем минимальное по стоимости (по весу) ребро и включаем его в список ребер. Соответствующие две вершины объединяем в одну компоненту связности.

4. Берем следующее по стоимости ( весу) ребро, добавляем к содержимому предыдущей строчки левого столбца; объединяем компоненты связности. Если концы ребра уже принадлежат одной и той же компоненте связности, то данное ребро в состав минимального остова не включается.

5. Повторяем эти операции до тех пор, пока все вершины не окажутся в одной единственной компоненте связности (для этого потребуется включить в состав остова ровно n–1 ребро).

Текст программы на языке Pascal

...

Результаты работы программы

Остов минимального веса:

( 4, 1 ) : 2

( 6, 7 ) : 3

( 3, 5 ) : 3

( 3, 0 ) : 3

( 7, 9 ) : 4

( 7, 2 ) : 4

( 7, 5 ) : 6

( 9, 8 ) : 7