Question

Do prim's and kruskal's algorithms always generate a unique minimum spanning tree? Please discuss in terms of both the structure of the graph and its cost.

0 4 4 6

Answer 1

Given network Prims Algorithm: The two most popular algorithms for minimum spanning tree are i) Prims Algorithm ii) Kruskal's Algorithm Prims algorithm to find minimum cost tree using greedy approach. Prims Algorithm: 1. The Given Network diagram is shown above 2. Choose the vertex, Here I am choosing vertex 6 3. Choose shortest edge from this vertex 6 4. Choose the nearest Vertex, not yet in the solution 5. Choose the next nearest vertex, not yet in the solution, when there is a choice choose either. Again choose next nearest vertex, make sure, cycle should not be formed in spanning tree Again choose next nearest Vertex Total cost of all edges = 14 Hence we Covered all the vertecies, and obtained the minimal spanning. * The Time complexcity of prims Algorithm is O(r logV + Elogv) = O(E log V). Kruskal's Algorithm: In Kruskal's Algorithm at each stage, you look at globally smallest edge that doesnot create a cycle in the given network. 1. The given Network is 2. Choose the shortest edge if(there is more than one Choose any of the shortest The shortest edges we have (2, 3), (2, 6) we can choose either of the two. 3. Choose the next shortest edge and add it 4. Choose the next shortest edge, make sure it wouldn't Create a cycle, and add it 5. Again choose the shortest edge, and to it 6. Repeate until all the vertices are covered, and minimum spanning tree is obtained

Hope this will help