大连理工大学算法分析与设计ch6-5动态等价关系-1s-[兼容模式]

6.6动态等价关系与并查集动态等价关系在求解实际应用问题时常会遇到等价类问题。从数学上看，等价类是一个对象(或成员)的集合，在此集合中所有对象应满足等价关系。若用符号R表示集合上的等价关系，那么对于该集合中的任意对象x,y,z，下列性质成立：自反性：xRx。对称性：若xRy,则yRx。传递性：若xRy且yRz,则xRz。因此，等价关系是集合上的一个自反、对称、传递的关系。≡≡动态等价关系“相等”(=)就是一种等价关系，它满足上述的三个特性。图中顶点的连通也是一种等价关系动态等价关系设R是集合S上的等价关系，对任何x∈S，令[x]R={y|y∈S∧xRy}。则[x]RS，称为由x∈S生成的一个R等价类。一个集合S中的所有对象可以通过等价关系划分为若干个互不相交的子集S1,S2,S3,…，它们的并就是S。这些子集即为等价类确定等价类的方法假设：集合S中含有n个元素，m个形如(x,y)(x,y∈S)的等价偶对。求S的划分。集合S中每个元素各自形成一个只含单个成员的子集，记作S1,S2,S3,…Sn。依次读入m个偶对(x,y)：若x∈Si,y∈Sj,Si≠Sj，则Si并入Sj,将Si置空。-----find(x)------ISx≡≡y？-----union(t,u)-----MAKE生成树假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。BACDFEBACDFE最小生成树最小生成树：带权图的生成树上的各边权值之和称为这棵树的代价。最小代价生成树是各边权值的总和最小的生成树。Kruskal算法的基本步骤设G＝(V,E),T为G的最小生成树，初态T＝(V,{})按照边的权值由小到大的顺序，考察G的边集E中的各条边。n个顶点m条边：加一条边后判断是否有回路：深度优先搜索{v0},{v1},{v2},{v3},{v4},{v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1},{v0,v2},{v3},{v4},{v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1},{v0,v2},{v3},{v4},{v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1},{v0,v2},{v3,v5},{v4}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1},{v0,v2},{v3,v5},{v4}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2},{v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2},{v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2,v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2,v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2,v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4},{v0,v2,v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5){v1,v4,v0,v2,v3,v5}v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)