2015-10-22
716
Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графа. Алгоритм було вперше описано Джозефом Крускалом 1956 року.
Візьмемо зважений зв'язний граф G=(V,E), де V — множина вершин, E — множина ребер, для кожного з яких задано вагу. Тоді ациклічна множина ребер, що поєднують усі вершини графа і чия загальна вага мінімальна, називається мінімальним каркасним (або кістяковим) деревом.
Алгоритм Крускала починається з побудови виродженого лісу, що містить V дерев, кожне з яких складається з однієї вершини. Далі виконуються операції об'єднання двох дерев, для чого використовуються найкоротші можливі ребра, поки не утвориться єдине дерево. Це дерево і буде мінімальним кістяковим деревом.
Алгоритм Прима - алгоритм побудови мінімального кістякового дерева. Це жадібний алгоритм.
- Спочатку ребра сортують за зростанням ваги.
- Додають найменше ребро в дерево.
- Зі списку ребер із найменшою вагою вибирають таке нове ребро, щоб одна з його вершин належала дереву, а інша — ні.
- Це ребро додають у дерево і знову переходять до кроку 3.
- Робота закінчується, коли всі вершини будуть у дереві.
