总结一下就是:
· 点的合并
· 图的分割
使用深度优先、广度优先来分割连通子图。
有兴趣可以自己尝试实现一下,我们不做详细讨论。
简单介绍一下并查集。
· 节点:一开始每个人都是自己的老板。
· 查找:从一个人开始,找到终极老板(老板是自己的人)
· 合并:如果两个人的终极老板不是同一个人,随便推举一个终极老板作为另一个终极老板的老板。
· 路径压缩:如果一个人的老板不是终极老板,把终极老板作为自己的老板。
代码实现:
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的边并联等等情况时,使用并查集扩展起来就很简单了。