(Просто ради прозрачности хочу сразу же упомянуть, что это домашняя задача).
У меня есть набор (x, y) точек, включая конкретную начальную точку.Я хочу найти сеть самой короткой общей длины, чтобы каждая точка достигалась от начальной точки.
Я знаю, что это отражает MST на графике, но проблема в том, что точки не расположены вграфик, а скорее не связаны между собой.Я знаю, что мог бы найти действительный MST, соединив каждую точку с любой другой точкой и запустив Prim-Jarnik, но в этом случае простое создание графа было бы O (n ^ 2) для количества точек в наборе, верно?
Я нашел похожий вопрос , но он рекомендует использовать то, что называется триангуляцией Делоне, для создания графика из точек, а затем запустить на нем Prim-Jarnik.Я почти уверен, что это выходит за рамки того, что ожидает от меня мой курс, учитывая, что это курс по вводным алгоритмам / структурам данных и что об этом никогда не упоминалось.
Есть ли более эффективный способ найти решение, чем создание графика за n ^ 2 времени и затем запуск Prim-Jarnik (без расширенной геометрии), или это лучшее, что мы можем сделать?