double arrow

Методи побудови екстремальних дерев. Алгоритм Краскала та Прима (самостійно).


Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графа. Алгоритм було вперше описано Джозефом Крускалом 1956 року.

Візьмемо зважений зв'язний граф G=(V,E), де V — множина вершин, E — множина ребер, для кожного з яких задано вагу. Тоді ациклічна множина ребер, що поєднують усі вершини графа і чия загальна вага мінімальна, називається мінімальним каркасним (або кістяковим) деревом.

Алгоритм Крускала починається з побудови виродженого лісу, що містить V дерев, кожне з яких складається з однієї вершини. Далі виконуються операції об'єднання двох дерев, для чого використовуються найкоротші можливі ребра, поки не утвориться єдине дерево. Це дерево і буде мінімальним кістяковим деревом.

Алгоритм Прима - алгоритм побудови мінімального кістякового дерева. Це жадібний алгоритм.

  1. Спочатку ребра сортують за зростанням ваги.
  2. Додають найменше ребро в дерево.
  3. Зі списку ребер із найменшою вагою вибирають таке нове ребро, щоб одна з його вершин належала дереву, а інша — ні.
  4. Це ребро додають у дерево і знову переходять до кроку 3.
  5. Робота закінчується, коли всі вершини будуть у дереві.

Сейчас читают про: