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

Теория сложности вычислительных процессов и структур
Лабораторная работа №1
Поиск минимального остова графа
Присылаемый на проверку архив должен содержать 2 файла:
 файл отчета, содержащий титульный лист, условие задачи, описание алгоритма Краскала, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
 файл с исходным текстом программы (программу можно писать на любом языке программирования).

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

2. Теоретическая часть и описание алгоритма Краскала
Минимальный остов (или остовное дерево минимального веса, MST) — это подграф данного связного взвешенного неориентированного графа, который содержит все его вершины, является деревом (связен и не содержит циклов) и имеет минимально возможную сумму весов входящих в него рёбер.
Алгоритм Краскала относится к категории «жадных» (greedy) алгоритмов и состоит из следующих шагов:
1. Инициализация: каждая вершина графа изначально объявляется отдельной связной компонентой (изолированным деревом). Создается пустое множество рёбер для будущего остова.
2. Сортировка рёбер: выписываются все существующие рёбра графа с их весами, после чего они сортируются в порядке строгого возрастания их весов.
3. Перебор и добавление рёбер: последовательно рассматриваются рёбра из отсортированного списка:
o Если текущее ребро соединяет вершины, находящиеся в разных компонентах связности, оно добавляется в остов, а эти две компоненты объединяются в одну.
o Если вершины ребра уже принадлежат одной компоненте, то добавление ребра приведет к образованию цикла. Такое ребро игнорируется.
4. Критерий остановки: Процесс завершается, когда в остов будет добавлено ровно (V - 1) рёбер, где V — количество вершин графа (для графа из 10 вершин в остове должно быть ровно 9 рёбер).

3. Исходные данные (Вариант 6)
Граф состоит из 10 вершин (пронумеруем их от 1 до 10). Матрица смежности из задания имеет вид:
Вершины 1 2 3 4 5 6 7 8 9 10
1 0 0 24 0 14 16 24 13 16 0
2 0 0 9 23 6 26 19 0 10 27
3 24 9 0 14 5 23 22 19 8 10
4 0 23 14 0 22 7 16 5 11 25
5 14 6 5 22 0 15 18 22 23 26
6 16 26 23 7 15 0 29 0 23 21
7 24 19 22 16 18 29 0 4 8 26
8 13 0 19 5 22 0 4 0 8 7
9 16 10 8 11 23 23 8 8 0 28
10 0 27 10 25 26 21 26 7 28 0

Лабораторная работа 1 20.09.2026 20.09.2026 Зачет Уважаемый, замечаний нет. Галкина Марина Юрьевна