How to Apply Union-Find for Point Merging and Graph Partitioning in Circuit Simulations

Problem Description: Previously we discussed using a circular doubly‑linked list to record connections between component terminals. Before solving the circuit, we need to treat terminals that are electrically the same as a single point, merge zero‑resistance component terminals, and finally identify all connected sub‑graphs for independent calculation.

Method 1

Use depth‑first search to merge points and use depth‑first or breadth‑first traversal to split connected sub‑graphs. The implementation is left as an exercise.

Union-Find

A concise introduction to the disjoint‑set data structure:

Node: each element initially points to itself as its own parent.

Find: follow parent links until reaching the root (an element that is its own parent).

Union: if two roots differ, make one root the parent of the other.

Path compression: after finding the root, attach intermediate nodes directly to the root.

Code implementation:

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;
  }
}

Point Merging

Combine the circular doubly‑linked list with Union‑Find to record point connections. This allows point merging to be handled within the connection logic without recomputing the whole graph each time.

Graph Splitting

To obtain connected sub‑graphs:

Traverse all points; if a point and its root belong to different graphs, merge those graphs.

Traverse all edges; if the two vertices of an edge belong to different graphs, merge those graphs.

Each distinct root represents a connected sub‑graph.

Conclusion

Using Union‑Find for point merging does not outperform depth‑first traversal in raw speed, but when combined with a circular doubly‑linked list it embeds merging into the connection/disconnection logic, avoiding repeated full‑graph calculations. Union‑Find based graph splitting is not the most optimal in terms of efficiency, yet its logic is simple and easily extensible—for example, handling short‑circuit or zero‑resistance edges becomes straightforward.