Надеюсь, вы знакомы с MST Прима. Вы можете увидеть постановку задачи здесь. Я решал эту проблему два раза год назад, не зная стандартного способа решения. Сегодня я снова попытался решить эту проблему, но мне потребовалось много времени, поэтому я решил узнать стандартный способ сделать это, чтобы я мог его запомнить.
В MST Prim вы должны выбрать ребра из всех доступных ребер между всеми узлами так, чтобы все узлы были соединены и был только один возможный путь между любыми двумя узлами, а сумма всех ребер была минимальной. Чтобы решить эту проблему, мы берем два набора, один из которых содержит mst (с этого момента я буду называть его mstSet), а другой, который еще не включен в MST, но должен быть включен. mst от установщика задачи, но чтобы сделать mst, мы можем выбрать любую точку в качестве отправной точки, но в этом случае порядок ответа не будет таким же, как у установщиков задачи. В теории графов мы используем термин разрез, это группа ребер, соединяющих точки в одном наборе с другим. Мы установим расстояние между всеми узлами от s до бесконечности. Предположим, наша начальная точка в mstSet s связана с точками a, b и c, которые еще не включены в mstSet. Итак, наш разрез содержит ребра s - a, s - b и s - c. Теперь мы выберем край с минимальным расстоянием от другого конца (то есть не в MST) от источника s (наша начальная точка) от разреза и поместим другой конец края (предположим, a) в mstSet. Теперь предположим, что a связано с d и e. Теперь мы обновим расстояние Теперь доступные ребра в нашем разрезе: s - b, s - c, a - d и a - e. Мы снова выбираем край с минимальным расстоянием другого конца края от s и помещаем его в наш mstSet. Мы повторяем этот шаг, пока наш mstSet не будет содержать все узлы дерева.
Почему это работает?
Собственно, выше мы применили жадный алгоритм. На каждом этапе мы брали минимум всех доступных вариантов.
