matlab минимальное связующее дерево keep busy

Question

Я использую функцию grMinSpanTree в наборе инструментов Matlab. Но, когда число узлов велико, выполнение кода не заканчивается, оно остается навсегда занятым.

Я пробовал много образцов, и все они хорошо работают, когда количество узлов ниже 4000. Но когда я пытаюсь использовать один из 8000 узлов, я запускаю несколько часов и не получаю результата.

Я только начинаю для теории графов и matlab. Есть ли причина, которая может вызвать мертвую петлю?

Answer 1

Если E - количество ребер, а V - количество вершин, этот жадный алгоритм работает в O(E * V).

Следовательно, рост времени квадратичен, когда E и V увеличение. Нет мертвой петли.

Кроме того, необходимое пространство памяти также увеличивается и может привести к замене вашего компьютера, что значительно увеличит общее время.