Прямолинейное остовное дерево: различия между версиями

Экспериментальные результаты построения прямолинейного остовного графа на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [ ]: для каждой точки просканировать все остальные точки, но установить связь только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время исполнения. Если количество точек на входе было больше 10000, подходу на основе полного графа попросту не хватало памяти.