In Kruskal's algorithm , sort all edges first , assume each node is a tree so you have a forest in the beginning. Take minimum edge at each step while it does not cause a cycle. You reached a single tree at the end.
In Prim's algorithm , start from an arbitrary vertex, grow your connected tree with one node at each step. Look for a minimum distance from all the nodes of our connected tree to other nodes which is not added yet.
- MST is not necessarily the shortest path and it does not apply to cycle.
- Kruskal’s has better running times if the number of edges is low, while Prim’s has a better running time if both the number of edges and the number of nodes are low.
- So, of course, the best algorithm depends on the graph and if you want to bear the cost of complex data structures.
Questions :
1 - There are 1 example Kruskal's algorithm and 1 example Prim's algorithm here :
http://www.cs.rit.edu/~lr/courses/alg/student/1/minspan.pdf
2 - 2 Kruskal example here : http://www.comp.dit.ie/rlawlor/Alg_DS/MST/Kruskal.pdf
3 - 3rd question here : https://hkn.eecs.berkeley.edu/examfiles/cs170_fa04_mt1_sol.pdf
4 - 1st question - (8) & (9) : http://www.cs.toronto.edu/~vassos/teaching/c73/old-exams/midterm-13.pdf
5 - 3rd question : http://www.cs.toronto.edu/~vassos/teaching/c73/old-exams/midterm-10.pdf
Hiç yorum yok:
Yorum Gönder