На другому занятті обласної школи олімпійського резерву з програмування 21 жовтня були розглянуті основні поняття теорії графів та алгоритм Прима-Крускала знаходження мінімального остовного дерева.
Алгоритм Прима-Крускала
Розглянемо задачу. На території плоскої країни розташовано n міст. Потрібно з’єднати всі міста телефонним зв’язком так, щоб загальна довжина телефонних ліній була мінімальною.
Алгоритм знаходження мінімального остовного дерева використовує "жадібну" стратегію – на кожному кроці обирається й додається до дерева, що будується, ребро з найменшою вагою, яке не утворює циклів з уже обраними ребрами.
Перевірка того, що ребро не утворює циклів, може виконуватися за допомогою прийому, який називають розфарбуванням графу. Він полягає в тому, що кожній вершині графа умовно дається колір, закодований числом. Якщо ребро додається до остовного дерева, то його кінці й усі пов’язані з ними вершини остовного дерева перефарбовуються в однаковий колір. Кандидатами на додавання до остовного дерева будуть лише ті ребра графа, кінці яких пофарбовані у різні кольори.
Якщо граф має n вершин, то мінімальне остовне дерево буде складатися з n – 1 ребра, тобто виконання алгоритму завершується за n – 1 крок.
Опис основних понять теорії графів та алгоритму Прима-Крускала - тут.
Немає коментарів:
Дописати коментар