开发者

How might Union/Find data structures be applied to Kruskal's algorithm?

htt开发者_如何学Pythonp://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

Union/Find data structure being used for disjoint sets...


It is stated in the entry for Kruskal's algorithm, but you can use the union/find structure to test (via FIND) if the edge connects two different trees or whether it will form a cycle when added.

The same structure can be updated (via UNION) if the edge does not form a cycle and is added to the spanning tree.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜