Mst

[shekabdulla]

hi friends,

i want to convert a MST obtained by Kruskal's algorithm to a rooted tree,
and count number of descendants of every vertex.any arbitrary vertex can be taken as a root vertex.

thanks in advance

[Wenter]

That tree as you told in your post's last statement turns out to be an unrooted tree, Kruskal algorithm is not the most optimized one for MST, i guess.Plus, if you want to count vertex, why not delve into the Kruskal with reference counter iterated and that you might want to again take a look at journals, recent research papers out there should shed some more light on what you are trying to accomplish.

[savlord]

Undirected and acyclic, I hope. Would this work? - Assume any leaf of the MST as the root. Then do a depth first search, constructing the tree as you go down. The number of descendants should be simple after that.

[Andreas Masur]

[ Moved thread ]