kruskal算法如何判断两个端点是不是属于一棵树?(用集合的话,不够大怎么办?)

1个回答

  • 给每个子树一个不同的编号,对每一个顶点引入一个标记t,表示这个顶点所在的子树编号.当加入一条红色边,就会使该边两端点所在的两个子树连接起来,成为一个子树,从而两个子树中的顶点标记要改变成一样.综上,可将Kruskal算法细化使其更容易计算机实现.

    kruskal应该是递归算法吧,在定义图中各端点时,可以多设一个标记,把图递归遍历一遍,在同一连同子图上的点,标记为一样的整型数值即可.