问题描述

之前我们已经讨论过用循环双向链表来记录元件端点之间的连接关系，在进行计算求解之前，我们还要做一些处理，把连接到一起的端点看做是一个点，如果元件的电阻是0的话，元件的两个端点也要看做是一个点，最后还要找到所有的连通子图，每一个连通子图单独进行计算。

总结一下就是：

• 点的合并

• 图的分割

方法1

使用深度优先遍历来合并点。

使用深度优先、广度优先来分割连通子图。

有兴趣可以自己尝试实现一下，我们不做详细讨论。

并查集

关于并查集的资料，很好找到，推荐“超有爱的并查集”，讲的通俗易懂。

简单介绍一下并查集。

• 节点：一开始每个人都是自己的老板。

• 查找：从一个人开始，找到终极老板（老板是自己的人）

• 合并：如果两个人的终极老板不是同一个人，随便推举一个终极老板作为另一个终极老板的老板。

• 路径压缩：如果一个人的老板不是终极老板，把终极老板作为自己的老板。

代码实现

class UnionFindSet {

  public get root(): UnionFindSet {
    return this.getRoot();
  }

  public set root(_root: UnionFindSet) {
    this._root = _root;
  }

  private _root: UnionFindSet;

  constructor() {
    this._root = this;
  }

  public destroy() {
    this._root = null;
  }

  public isRoot(): boolean {
    return this._root === this;
  }

  private getRoot(): UnionFindSet {
    if (this._root._root !== this._root) {
      let root: UnionFindSet = this._root._root;
      while (root !== root._root) {
        root = root._root;
      }
      let son: UnionFindSet = this._root;
      let temp: UnionFindSet;
      while (son !== root) {
        temp = son._root;
        son._root = root;
        son = temp;
      }
      this._root = root;
    }
    return this._root;
  }
}

点的合并

可以将循环双向链表和并查集联合起来使用，来记录点之间的连接关系。 有兴趣可以试试。

图的分割

这个就简单了。

• 遍历所有的点，如果点和其根节点属于两个不同的图，合并两个图。

• 遍历所有的边，如果边的两个顶点属于两个不同的图，合并两个图。

• 找到所有根图，每一个根图就是一个连通子图。

总结

使用并查集进行点的合并并不比深度优先遍历效率高，但是我们结合循环双向链表，把点的合并放到了点的连接和断开的逻辑中，不用每次都重新计算。

使用并查集分割连通子图效率上并不是最优的，但是使用并查集，逻辑简单，易扩展。比如当我们加入边的短路断路，两个电阻是0的边并联等等情况时，使用并查集扩展起来就很简单了。