Minimum Spanning Tree
Minimum Spanning Tree Let us deduce the problem of finding minimum spanning tree from a given graph, for that we need to know how tree is different from a graph and what minimum spanning tree actually is... So let us go by the definition, A graph is set of nodes and edges where as a tree is a set of nodes and vertices with no cycles, so the only thing in which a tree differs is on the fact that tree's does not contains cycles. If tree does not contain cycles, then it basically means that, we need to remove the cycles to convert a graph into a tree and so if we want a minimum spanning tree then we need to remove the edges forming a cycle with larger weight , i.e we only keep the edges with minimum weight , in the graph and keep including the edges which does not form a cycle, until all the edges are considered. So this method is basically Kruskals Method for finding Minimum Spanning Tree. Tap on the black frame below to see what Minimum Spanning Tree actually is: ...
