Алгоритми та структури даних · Senior · Запитання 5 з 75
Чим відрізняються алгоритми Прима й Крускала?
- ✓Правильна відповідь: Прим вирощує одне дерево з вершини; Крускал зливає ліси найдешевшими ребрами
- 2Прим шукає найкоротші шляхи; Крускал - кістякові дерева
- 3Приму потрібні відсортовані ребра; Крускалу - черга вершин із пріоритетом
Пояснення
Обидва будують мінімальне кістякове дерево. Прим додає найдешевше ребро, що виходить із поточного дерева (купа ребер); Крускал сортує всі ребра й через union-find пропускає цикли. Крускал природний для розріджених списків ребер, Прим - для щільних графів.