Skip to main content

Posts

Featured

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.


So to find a minimum spanning tree , we have to follow some simple steps which are stated as…

Latest posts

Community Detection

Semantic Networks

Markov Chain

Network Theory

Quick Sort

Improving search speed in Singly Linked List

Divide and Conquer Paradigm

Merge Sort

Insertion Sort

Bubble Sort