最近几年来，地理信息系统无论是在理论上还是应用上都处在一个飞速发展的阶段。 GIS被应用于多个领域的建模和决策支持，如城市管理、区划、环境整治等等，地理信息成为信息时代重要的组成部分之一； “数字地球”概念的提出，更进一步推动了作为其技术支撑的GIS的发展。 与此同时，一些学者致力于相关的理论研究，如空间感知、空间数据误差、空间关系的形式化等等。 这恰好说明了地理信息系统作为应用技术和学科的两个方面，并且这两个方面构成了相互促进的发展过程。
This section introduces the basic operations, query and merge, and determine whether or not to join based on the structure of the query set in the previous section.
The collection number of the query element, which is returned directly id Array valu O(1) The time complexity of.
... private int find(int p) { assert p >= 0 && p < count; return id[p]; } ... Merge element p And elements q For the collection to which it belongs, the merging process requires traversing all the elements, and then merging the set numbers of the two elements. This process is O(n) Complexity.
... public void unionElements(int p, int q) { int pID = find(p); int qID = find(q); if (pID == qID) return; for (int i = 0; i < count; i++) if (id[i] == pID) id[i] = qID; } ... 5.23.1. Java instance code ¶
源码包下载： Download UnionFind1.java file code: ¶
package runoob.union; /*\* \* 第一版union-Find */ public class UnionFind1 { // 我们的第一版Union-Find本质就是一个数组 private int[] id; // 数据个数 private int count; public UnionFind1(int n) { count = n; id = new int[n]; // 初始化, 每一个id[i]指向自己, 没有合并的元素 for (int i = 0; i < n; i++) id[i] = i; } // 查找过程, 查找元素p所对应的集合编号 private int find(int p) { assert p >= 0 && p < count; return id[p]; } // 查看元素p和元素q是否所属一个集合 // O(1)复杂度 public boolean isConnected(int p, int q) { return find(p) == find(q); } // 合并元素p和元素q所属的集合 // O(n) 复杂度 public void unionElements(int p, int q) { int pID = find(p); int qID = find(q); if (pID == qID) return; // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并 for (int i = 0; i < count; i++) if (id[i] == pID) id[i] = qID; } }