го графа. Алгоритм вперше був відкритий в 1930 році чеським математиком Войцехом Ярніка, пізніше перевідкритий Робертом прийму в 1957 році, і, незалежно від них, Е. Дейкстрой в 1959 році.
Побудова починається з дерева, що включає в себе одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить всі вершини вихідного графа. На кожному кроці алгоритму до поточного дереву приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину не з дерева. p align="center"> 1 Алгоритм Краскала
1.1 Опис алгоритму Краскала
Формулювання.
Спочатку поточне безліч ребер встановлюється пустим. Потім, поки це можливо, проводиться наступна операція: з усіх ребер, додавання яких до вже наявного безлічі не викличе поява в ньому циклу, вибирається ребро мінімальної ваги і додається до вже наявного безлічі. Коли таких ребер більше немає, алгоритм завершений. Підграф даного графа, що містить всі його вершини та знайдене безліч ребер, є його остовне деревом мінімальної ваги. p align="justify"> Алгоритм складається з наступної послідовності дій:
. Створюється список ребер E, що містить довжину ребра, номер вихідної вершини ребра (i), номер кінцевої вершини ребра (j), ознака включення даного ребра в дерево.
2. Даний список впорядковується в порядку зростання довжин ребер.
. Проглядається список E і вибирається з нього ребро з максимальною довжиною, ще не включене в результуюче дерево і не утворить циклу з вже побудованими ребрами.
. Якщо всі вершини включені в дерево і кількість ребер на одиницю менше кількості вершин, то алгоритм свою роботу закінчив. В іншому випадку здійснюється повернення до пункту 3.
1.2 Псевдокод алгоритму
Відсортувати ребра в порядку зростання ваг
ініціалізувати структуру разбиений
edgeCount = l
while edgeCount <= E and includedCount <= М-l do
parentl = FindRoot (edge ​​[edgeCount]. start) = FindRoot (edge ​​[edgeCount]. end) parentl/= parent2 then
додати edge [edgeCount] в кістяк = includedCount = l (parent1, parent2) if = edgeCount + lwhile. - Число ребер в графі;
V - число вершин у графі
edgeCount - змінна;
includedCount - змінна; - масив, в якому під кожен елемент множини, з яким ми збираємося працювати, відведена одна клітинка;
FindRoot (x) - (x елемент, для якого ми хочемо знайти корінь частини, його...
