The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.
The algorithm can be described as follows:
sort edges in order of increasing cost | |
MST = {} | |
foreach edge (u, v) in order of increasing cost | |
if MST ∪ (u, v) does not create a cycle | |
add (u, v) to MST | |
return MST |
Checking for cycles can be done with the help of union-find/disjoint set data structure. Initially, each vertex is in its own set. When we are trying to add an edge (u, v) to the MST, we first check if they belong to the same set in which case adding that edge will create a cycle. If they don’t belong to the same set, we add the edge to the MST and merge the sets containing the vertices u and v.
Running time analysis: Sorting takes time O(E log E) and each query to the union-find data structure takes time O(log* V). Since there are E such queries, the overall running time is O(E log E + E log* V) = O(E log E) = O(E log V) (since E is at most V^{2}) i.e., time for sorting dominates the overall running time of the algorithm. If the edges are already sorted, then running time reduces to O(E log* V).
Take a look at the C++ implementation.
Try your hand at problem MST, which uses this idea.
Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne
Pingback: Union Find / Disjoint Set data structure C++ implementation | Everything Under The Sun
Pingback: Prim’s Minimum Spanning Tree Algorithm | Everything Under The Sun
I was challenged by a professor of mine to implement this algorithm on a parallel machine. I haven’t done it, but I’m planning on doing so. Might be a hint! 🙂
hey buddy i tried to implement this program and took contents of text file from mentioned site, it doesn’t gets executed it says kruskal.cpp stopped working..
Did you take the input from the sample test case given here: http://www.spoj.com/problems/MST/ ?
This problem supplies vertices in 1-based representation and the code takes vertices in 0-based representation. To make the code work for this problem, subtract off 1 from edges[i]->u and edges[i]->v after line 77.
Still having the same problem, i did like edges[i]->u-1;
Add these two lines after line 77:
–edges[i]->u;
–edges[i]->v;
Contents of input1.txt file:-
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40
ok, it is working now. But in case of prims it shows like zero for both.
It’s working with Prim’s as well. Just add this line after line 116:
–u; –v;
For prims doing this make works:- u=u-1; v=v-1;
for kruskal doing this make works:-edges[i]->u=edges[i]->u-1; edges[i]->v=edges[i]->v-1;
Yeah. I’ve already mentioned that in my replies.
yes thanks , can you please tell me if eager version can be changed to lazy or not ?
Yes we can and it’s much easier to implement as well. It does not require Indexed priority queue and works with normal priority queue. Instead of changing the weight for reaching a new vertex (in eager version), we just add the new vertex with the reduced weight onto the queue. To understand their differences and see and implementation, look here: http://algs4.cs.princeton.edu/43mst/
OK so I went through the link, now what all should I change to make it as a lazy version ?
You no longer need to use Indexed priority queue but can use standard priority queue that comes with your language of choice. A sample solution in C++: https://github.com/kartikkukreja/blog-codes/blob/master/src/Lazy%20Prim's%20MST%20algorithm.cpp
It gets accepted for http://spoj.com/problems/MST
Ok, but the above code doesn’t takes any file so theres is no output.
For that, you just need to write this line at line 14:
freopen(“input.txt”, “r”, stdin);
and give input in a file named “input.txt”.
in line 14 of lazy prims i pasted freopen(“input1.txt”, “r”, stdin) and its working now, thanks for helping me..
I would like to is there any way to calculate how much time these programs will take for vertices and edges more then 500 and 1000 ?
Complexity of MST problem is O(E log V), which is extremely fast. If you can store the graph in memory, you can find its MST very quickly so you’d be bounded by how much you can store in memory.