Алгоритми та структури даних · Middle · Запитання 65 з 75
Який алгоритм будує мінімальне кістякове дерево, додаючи найдешевші ребра, що не створюють циклу?
- 1Топологічне сортування
- ✓Правильна відповідь: Алгоритм Крускала
- 3Алгоритм Дейкстри
Пояснення
Крускал сортує ребра за вагою й за допомогою union-find пропускає ребра, що з'єднали б вершини вже однієї компоненти. Дейкстра шукає найкоротші шляхи, а це інша задача.