Реализация алгоритмов Краскала и Прима для построения минимального остовного дерева взвешенного связного неориентированного графа. Анализ трудоемкости алгоритмов, их псевдокоды и тестирование. Применение алгоритма Краскала на практике в работе авиалиний.
Аннотация к работе
1 Алгоритм Краскала 1.1 Описание алгоритма Краскала 1.2 Псевдокод алгоритма 1.3 Блок-схема алгоритма 1.4 Сложность алгоритма 2. Алгоритм Прима 2.1 Описание алгоритма Прима 2.2 Псевдокод алгоритма 2.3 Блок-схема алгоритма 2.4 Код программы 2.5 Оценка сложности Заключение Список использованных источников Введение Объектом исследования курсовой работы стала реализация алгоритма Краскалы. Целями работы являлись: 1) ознакомление с алгоритмом Краскалы, его историей; 2) реализация алгоритма, для построения минимального остовного дерева; 3) анализ трудоёмкости алгоритма; 4) тестирование алгоритма. Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.