C#中的Disjoint Set实现
发布时间:2020-12-15 21:07:46 所属栏目:百科 来源:网络整理
导读:我没有在C#中使用Union通过排名实现找到任何好的Disjoint Set实现,所以我实现了自己的.它适用于O(log n)时间复杂度. 是否更快(或在C#中内置实现)或我可以使用我自己的实现? class DisjointSetUBR{ int[] parent; int[] rank; // height of tree public Disj
我没有在C#中使用Union通过排名实现找到任何好的Disjoint Set实现,所以我实现了自己的.它适用于O(log n)时间复杂度.
是否更快(或在C#中内置实现)或我可以使用我自己的实现? class DisjointSetUBR { int[] parent; int[] rank; // height of tree public DisjointSetUBR(int[] arr) { parent = new int[arr.Length +1]; rank = new int[arr.Length + 1]; } public void MakeSet(int i) { parent[i] = i; } public int Find(int i) { while (i!=parent[i]) // If i is not root of tree we set i to his parent until we reach root (parent of all parents) { i = parent[i]; } return i; } // Path compression,O(log*n). For practical values of n,log* n <= 5 public int FindPath(int i) { if (i!=parent[i]) { parent[i] = FindPath(parent[i]); } return parent[i]; } public void Union(int i,int j) { int i_id = Find(i); // Find the root of first tree (set) and store it in i_id int j_id = Find(j); // // Find the root of second tree (set) and store it in j_id if (i_id == j_id) // If roots are equal (they have same parents) than they are in same tree (set) { return; } if (rank[i_id] > rank[j_id]) // If height of first tree is larger than second tree { parent[j_id] = i_id; // We hang second tree under first,parent of second tree is same as first tree } else { parent[i_id] = j_id; // We hang first tree under second,parent of first tree is same as second tree if (rank[i_id] == rank[j_id]) // If heights are same { rank[j_id]++; // We hang first tree under second,that means height of tree is incremented by one } } } } 解决方法
>在塞奇威克教授的“算法”一书中,他将
mentions加权快速联合 路径压缩“应该具有反向Ackermann函数的find / union的摊销时间. >你是对的,在.Net中没有任何Disjoint Set的实现.
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |