notes figure sixteen spanning trees of complete graph on four vertices now suppose the edges of the graph have weights or lengths the weight of tree is just the sum of weights of its edges obviouslydifferent trees have different lengths the problemhow to find the minimum length spanning treethis problem can be solved by many different algorithms it is the topic of some very recent research there are several "bestalgorithmsdepending on the assumptions you makea randomized algorithm can solve it in linear expected time it can be solved in linear worst case time if the weights are small integers otherwisethe best solution is very close to linear but not exactly linear the exact bound is ( log beta( , )where the beta function has complicated definitionthe smallest such that log(log(loglog( ))is less than /nwhere the logs are nested times these algorithms are all quite complicatedand probably not that great in practice unless you're looking at really huge graphs here we'll go through two simple classical algorithms kruskal' algorithm we'll start with kruskal' algorithmwhich is easiest to understand and probably the best one for solving problems by hand kruskal' algorithm is an algorithm in graph theory that finds minimum spanning tree for connected weighted graph this means it finds subset of the edges that forms tree that includes every vertexwhere the total weight of all the edges in the tree is minimized if the graph is not connectedthen it finds minimum spanning forest ( minimum spanning tree for each connected componentkruskal' algorithm is an example of greedy algorithm this algorithm first appeared in proceedings of the american mathematical society in and was written by joseph kruskal lovely professional university