21. Алгоритмы Краскала и “ближайшего соседа” построения “экономичного” дерева. Построение "экономичного" дерева
К списку вопросов
Существует ряд алгоритмов построения "экономичного" дерева:
Предположим матрица попарных расстояний известна.
Алгоритм Краскала:
1. Определяем все возможные и ранжируем по возрастанию.
2 .Реализуем ребром наименьшее из оставшихся расстояний, следя только за тем, чтобы не образовалось цикла.
Алгоритм ближайшего соседа:
1. Определяем все возможные и ранжируем по возрастанию
2. Реализуем минимальное ребро. Соединяем ближайшую вершину к уже соединенному поддереву.
К списку вопросов
