跳至主要內容

不相交集

linwu大约 3 分钟

不相交集

不相交集数据结构(也称为并查集或者合并-查找集)是一种跟踪一组元素划分为许多不相交(非重叠)子集的数据结构。它提供近乎常数时间的操作(受到阿克曼函数的限制)来添加新集合合并现有集合,以及确定元素是否在同一集合中。除了许多其他用途(见应用部分),不相交集在 Kruskal's 算法中起着关键作用,该算法用于查找图的最小生成树。

不相交集
不相交集

MakeSet 创建了 8 个单元素集合。

不相交集
不相交集

在进行了一些 Union 操作之后,一些集合被组合在一起。

完整代码

DisjointSetItem

export default class DisjointSetItem {
  /**
   * @param {*} value
   * @param {function(value: *)} [keyCallback]
   */
  constructor(value, keyCallback) {
    // 存储元素值
    this.value = value;
    // 键回调函数用于生成键
    this.keyCallback = keyCallback;
    // 父元素,默认为 null
    this.parent = null;
    // 子元素,初始为空对象
    this.children = {};
  }

  /**
   * @return {*}
   */
  getKey() {
    // 允许用户定义自定义键生成器。
    if (this.keyCallback) {
      return this.keyCallback(this.value);
    }

    // 否则,默认使用 value 作为键。
    return this.value;
  }

  /**
   * @return {DisjointSetItem}
   */
  getRoot() {
    // 如果当前元素是根元素,返回自身,否则返回父元素的根。
    return this.isRoot() ? this : this.parent.getRoot();
  }

  /**
   * @return {boolean}
   */
  isRoot() {
    // 如果 parent 为 null,则当前元素为根元素
    return this.parent === null;
  }

  /**
   * Rank基本上意味着所有祖先的数量。
   *
   * @return {number}
   */
  getRank() {
    // 如果没有子元素,rank 为 0
    if (this.getChildren().length === 0) {
      return 0;
    }

    let rank = 0;

    /** @var {DisjointSetItem} child */
    this.getChildren().forEach((child) => {
      // 计算子节点本身。
      rank += 1;

      // 也添加当前子节点的所有子节点。
      rank += child.getRank();
    });

    return rank;
  }

  /**
   * @return {DisjointSetItem[]}
   */
  getChildren() {
    // 返回所有子元素
    return Object.values(this.children);
  }

  /**
   * @param {DisjointSetItem} parentItem
   * @param {boolean} forceSettingParentChild
   * @return {DisjointSetItem}
   */
  setParent(parentItem, forceSettingParentChild = true) {
    // 设置父元素
    this.parent = parentItem;
    // 如果 forceSettingParentChild 为 true,则把当前元素添加到父元素的子元素中
    if (forceSettingParentChild) {
      parentItem.addChild(this);
    }

    return this;
  }

  /**
   * @param {DisjointSetItem} childItem
   * @return {DisjointSetItem}
   */
  addChild(childItem) {
    // 将元素添加到子元素
    this.children[childItem.getKey()] = childItem;
    // 将当前元素设置为添加的元素的父元素
    childItem.setParent(this, false);

    return this;
  }
}

DisjointSet

export default class DisjointSet {
  /**
   * @param {function(value: *)} [keyCallback]
   */
  // 构造函数,参数是键回调函数
  constructor(keyCallback) {
    this.keyCallback = keyCallback; // 键回调函数
    this.items = {}; // 存储元素
  }

  /**
   * @param {*} itemValue
   * @return {DisjointSet}
   */
  // 创建新的集合
  makeSet(itemValue) {
    const disjointSetItem = new DisjointSetItem(itemValue, this.keyCallback);

    if (!this.items[disjointSetItem.getKey()]) {
      // 如果元素尚未存在,添加新元素
      this.items[disjointSetItem.getKey()] = disjointSetItem;
    }

    return this;
  }

  /**
   * 查找集合的表示节点。
   *
   * @param {*} itemValue
   * @return {(string|null)}
   */
  find(itemValue) {
    const templateDisjointItem = new DisjointSetItem(itemValue, this.keyCallback);

    // 尝试查找元素本身
    const requiredDisjointItem = this.items[templateDisjointItem.getKey()];

    if (!requiredDisjointItem) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  /**
   * 按秩合并。
   *
   * @param {*} valueA
   * @param {*} valueB
   * @return {DisjointSet}
   */
  union(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error('一个或两个值不在集合中');
    }

    if (rootKeyA === rootKeyB) {
      // 如果两个元素已经在同一集合中,只需要返回其键
      return this;
    }

    const rootA = this.items[rootKeyA];
    const rootB = this.items[rootKeyB];

    if (rootA.getRank() < rootB.getRank()) {
      // 如果rootB的树更大,那么rootB成为新的根
      rootB.addChild(rootA);

      return this;
    }

    // 如果rootA的树更大,那么rootA成为新的根
    rootA.addChild(rootB);

    return this;
  }

  /**
   * @param {*} valueA
   * @param {*} valueB
   * @return {boolean}
   */
  // 判断两个值是否在同一个集合中
  inSameSet(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error('一个或两个值不在集合中');
    }

    return rootKeyA === rootKeyB;
  }
}

参考文献

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群