fig minimum weighted spanning tree the last introduced trees by using them in various algorithms like binary search the definition doesn' change from the last but treesin the context of graph theoryare subset of the set of all possible graphs tree is just graph without any cycles in additionit is relatively easy to prove that tree must contain one less edge than its number of vertices otherwiseit would not be tree clearly the graph in fig is not tree there are many cycles within the graph kruskal' paper presented an algorithm to find minimum weighted spanning tree for such graph figure contains minimum weighted spanning tree for the graph in fig with the tree edges highlighted in orange we don' say the minimum weighted spanning tree because in general there could be more than one minimum weighted spanning tree in this casethere is likely only one possible kruskal' algorithm is greedy algorithm the designation greedy means that the algorithm always chooses the first alternative when presented with list of alternatives and never makes mistakeor wrong choicewhen choosing in other wordsno backtracking is required in kruskal' algorithm the algorithm begins by sorting all the edges in ascending order of their weights assuming that the graph is fully connectedthe spanning tree will contain | |- edges the algorithm forms sets of all the vertices in the graphone set for each this copy belongs to 'acha