A MST is obviously a BST. In fact, a simply linear algorithm exists for BST.

It appears in CLRS problem 23-3, but I didn’t come up with it and just Google it. I stupid!!!

It looks like a divide and conquer algorithm.

Find the median of all edge weights Em.

Using a DFS to check whether there exists a spanning tree with edge weights not greater than Em.

If yes, remove all edges of weight greater than Em. Repeat.

If no, contract all edges of weight not greater than Em and get a smaller graph. Repeat.

Obviously, each edge is processed one time.

It appears in CLRS problem 23-3, but I didn’t come up with it and just Google it. I stupid!!!

It looks like a divide and conquer algorithm.

Find the median of all edge weights Em.

Using a DFS to check whether there exists a spanning tree with edge weights not greater than Em.

If yes, remove all edges of weight greater than Em. Repeat.

If no, contract all edges of weight not greater than Em and get a smaller graph. Repeat.

Obviously, each edge is processed one time.

Advertisements