matlab minimum spanning tree keep busy

Question

I use the grMinSpanTree function in matlab toolbox. But, when the number of nodes is high the code execution doesn't come to an end, it remains in forever busy state.

I tried a lot of samples and they all work well when number of nodes is below 4000. But when I try the one with 8000 nodes I run for several hours and still no result.

I am only beginner for graph theory and matlab. Is there any reason that may cause dead loop?

Answer 1

If E is the number of edges and V is the number of vertices, this greedy algorithm runs in O(E * V).

Therefore, the time growth is quadratic when E and V increase. There is no dead loop.

In addition, the memory space needed also increases and may force your computer to swap thus increasing dramatically the overall time.