the minimum spanning tree

What’s MST?

Today,I want to share an algorithm which called the “the minimum spanning tree”,shortly,”MST”.It’s a graph algorithm,which was used for solve a problem like this,“give you an undireted weighted graph,you should choose some edges to the connect the graph and make the cost is the cheapest”

How to sovle it?

Sounds difficult?Let’s try to solve it step by step.

First of all,we can deduce that the result of edges which we select can form a tree.why?

Concerned that if the results not a tree,we can remove some edges to make it still connect all points with the lower cost.But if we remove too much to make it impossible to form a tree,that will not satisfy the condition. Hence,the result must be a tree.

But how to calculate the tree?There is an algoriyhm called the Kruskal algorithm.

Let’s learn the procedure of it first ,then I will prove it’s correct.

The procedure of Kruskal:

1, Sort all the edges by the cost from cheap to dear.
2, Scanning the edges one by one,
	if the edge can connect two connect-block
		add it to the result set;
	else(that's the edge connect the same connect-block)
    	skip it;
    check the next edge,and repeat the above judgement.

Why it’s correct ?

Let me say one more words,the main idea of the above algorithm is called “greedy”,that’s it always take the lowest edge which connect two connected-block.

Anyway,let’s take our business.

Consider that we have formed the minimum spanning tree,however,we don’t have the cheapest ,maybe it’s the edge A-C,it doesn’t matter.But if we add the edge “A-C” to the result set,and remove one of the highest cost in A-B,B-C,it still satitify the condition but with a lower cost!That’s all.

How to code it?

the problem please click here

the code please click here