алгоритм Крукшала или алгоритм Примса, какой из них лучше при поиске минимального остовного дерева?

Я добавлю один балл в пользу алгоритма Прима, о котором я не упоминал. Если вам даны N точек и функция расстояния d (x, y) для расстояния между x и y, легко реализовать алгоритм Прима, используя пространство O (N) (но время N ^ 2).

Начните с произвольной точки A и создайте массив размером N-1, в котором указаны расстояния от A до всех других точек. Выберите точку B, связанную с кратчайшим расстоянием, свяжите A и B в остовном дереве, а затем обновите расстояния в массиве до минимума расстояния, уже отмеченного до этой другой точки, и расстояния от B до этой другой точки. точку, отмечая, где самая короткая ссылка от B, а где от A. Продолжайте.

Я не знаю аналогичного способа обработки алгоритма Крускала для плотного графа, заданного функцией расстояния, и для больших N у вас может закончиться пространство O (N ^ 2), прежде чем у вас закончится терпение на время O (N ^ 2).