5 5\n1 5 3\n1 2 1\n2 3 4\n3 4 5\n4 5 2\n\n10\n\nKaran starts from vertex (relative) 3,then goes to 2 (0+4), then 1 (0+4+1) ,then 5 (0+4+1+3) and then finally to relative 4 (0+4+1+3+2).\nTherefore,the total minimum cost incurred is 10.<\/code><\/pre>\nOBSERVATION:<\/h3>\n
The idea is simple, to visit all relatives by spending minimum cost means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.<\/p>\n
This is what Kruskal’s algorithm says.<\/p>\n
SOLVING APPROACH:<\/h3>\n
Visiting all the relatives by spending minimum cost is very similar to finding the minimum spanning tree for the given graph(the path diagram between each).<\/p>\n
Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).<\/p>\n
Follow these steps:<\/p>\n
\n- \n
Sort all the edges in non-decreasing order of their weight.<\/p>\n<\/li>\n
- \n
Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.<\/p>\n<\/li>\n
- \n
Repeat step 2 until there are (N-1) edges in the spanning tree.<\/p>\n<\/li>\n<\/ol>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645101854046-Article_371.png\")
<\/p>\n