问题6： 假如我们想知道原来未直接相 连的两个顶点一旦连起来就会 形成回路。应该如何解决？
如何实现 DISJOINT-SET 7
如何实现 DISJOINT-SET ？
Linked-list representation of disjoint sets (a) d head head $2 tail epresentative tail epresentative 操作union(g,e)执行后 head tail epresentative
操作union(g,e)执行后 Linked-list representation of disjoint sets representative representative representative
问题7： 为什么用链表实现，每个 操作的平均代价可能会是 线性的？ Union的顺序影响很大！
Union的顺序影响很大！
Operation Number of objects updated MAKE-SET(X1) MAKE-SET(X2) 1 : MAKE-SET(Xn) 1 Union操作对象 UNION(X2,X1) 1 的次序不影响结 UNION(X3,x2) 2 果，却影响效率 UNION(X4,X3) 3 这对你有什么启发？ : UNION(Xn,Xn-1) Figure 21.3 A sequence of 2n-1 operations on n objects that takes (n2)time,or (n)time per operation on average,using the linked-list set representation and the simple implementation of UNION
Union操作对象 的次序不影响结 果，却影响效率 这对你有什么启发？