which is better to use and also can the PRIMS be used when the graph is disconnected …
Use Prim’s algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
Source : link
You can’t really ask which algorithm is better in a given case without considering specific details of problem you are trying to solve.
Consider the following preconditions for using each to build a minimum spanning tree:
-
Prim’s - The graph must be : connected , weighted , undirected
-
Kruskal’s - The graph must be : connected, weighted
To answer your second question you cannot use Prim’s on a disconnected graph. The reasoning is hidden in the details of the algorithm. Since it works by starting at an initial vertex and connecting minimum adjacent edges until the graph spans all verticies. It seems to me that we would never be able to span all verticies if the graph contained even a single disconnected vertex.
2 Likes
Kruskal is O(ElogE + V*alpha2(V)) which is basically O(ElogE + V), works for directed graphs.
Prim is O(VlogV + ElogV), doesn’t work for undirected graphs. 99.99% of people in competitions won’t implement fibonacci heap, since it adds like 120 extra lines of code, so we can safely say this is it’s complexity.
I personally use kruskal becuase of several reasons:
-
It’s easier to code, at least for me
-
Works for directed graphs and without any modifications works for spanning forest, ie spanning trees of disconnected graphs. Prim’s can also be easily modified to work for second case, but Kruskal works without modifications. Minimum spanning tree of the entire graph is equal to sum of minimum spanning tree’s of each of it’s disconnected components, therefore Prim’s works in this case.
-
Disjoint Sets data structures allows solving some other sub-problems, aside from spanning tree. So it’s useful to know quickly how to code it.
-
Disjoint Sets, assuming you use path compression and rank heuristics + simple sorting, in practice, is without a question faster than maintaining a heap, and finding minimum in each step of the algorithm. They do have the same complexities however heap\binary tree or whatever you are using has a lot of extra computational overhead, while sorting doesn’t.
One advantage of Prim’s algorithm is that it has a version which runs in O(V^2). Consider a graph with V vertices and V*(V-1)/2 edges (complete graph). Then Kruskal’s runs in O(ElogE) = O(V^2logV^2), while Prim’s runs in O(V^2). So if E ~ V^2 (the graph is dense) then this “dumb” version of Prim’s algorithm which is O(V^2) can be used.
There are specific problems, which require one’s use over another, so you should know both of them). But in general case it doesn’t matter, it’s just a matter of preference. Generally Kruskal’s is faster, but the speed gain won’t matter all that much or at all in almost all of the competitions. So my suggestion is to go with the one you like and the one that’s easier to code for you.
1 Like
Fibonacci heap has no real use in contests, though. The heap data structure in C++ is decent enough to pass whatever’s necessary, and it’s in the STL, so there’s no need to code it, unlike with Fib. heap. And the Fibonacci heap can have a worse constant.
1 Like
Fun fact about logarithms: you don’t need to write exponents there, because log(xy)=log(x)+log(y), so log(x^k)=klog(x); if k is constant, you can remove it from the O-notation.
When looking for MST, we can get rid of multiple edges quickly when reading the input, so we can consider M <= N(N-1)/2 in the algorithm; it means that O(log M)=O(log N).