Which algorithm is best suited to find the minimum spanning tree
Kruskal algorithm or prim's algorithm?
Which has the lowest time complexity?
Please help.
Which algorithm is best suited to find the minimum spanning tree
Kruskal algorithm or prim's algorithm?
Which has the lowest time complexity?
Please help.
It really depends on your input. I would say Prim's is better if you have a graph with a lot more edges than vertices. However, this depends on the data structure you are using in your implementation. You should read more online about the different options. A Fibonacci heap is usually what is required for an optimum Prim implementation.
In any other cases I would go ahead and use Kruskal.
1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
3. Get rid of conio.h and other antiquated DOS crap headers.
4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.
I prefer Kruskal algorithm. It's realization with disjoint set union is much easiar to write, and it almost as quickly as Prim's algorithm with Fibonnaci heap.
Use Kruskal's algorithm when you're only dealing with a low number of edges. Otherwise use Prim's algorithm.