动态连通性问题

Posted on Edited on

问题：输入整数对‘p q’，如果不存在其他整数与p、q相连或者相连的整数不能连接到对方，则将p、q直接相连；否则认为p、q相连，不操作。

建立问题模型

对象关系：

  • 自反性：p与自身相连
  • 对称性：若p与q相连，则q与p也相连
  • 传递性：若p与q相连，q与r相连，则p与r相连

基本操作：

  • find：查询触点所在连通分量
  • union：合并两个连通分量

API设计：

1
2
3
4
5
6
7
8
9
10
11
public class UF {
  //ids存放触点，count对分量计数
  int[] ids;
  int count;
  
  UF(int N);							//initialize data structure
  int find(int p);						//查询所在分量
  boolean connected(int p,int q);		//are p and q in the same component?
  void union(int p,int q);				//add connection between p and q
  int count();							//number of components
}

算法实现及演变

1.quick-find

用数组索引表示原始对象，对应值表示所属分量。

查询快；

合并慢，每次都修改被合并分量中所有触点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class UF{
  int[] ids;
  int count;
  
  public UF(int N){
    ids = new int[N];
    for(int i=0; i<N; i++){
      ids[i] = i;
    }
    count = N;
  }
  
  public int find(int p){
    return ids[p];
  }
  
  public boolean connected(int p,int q){
    return ids[p] == ids[q];
  }
  
  public void union(int p,int q){
  	int pId = ids[p];
    int qId = ids[q];
    
    if(pId != qId){
      for(int i=0; i<ids.length(); i++){
        if(qid == ids[i]){
          ids[i] = pId;
        }
        count++;
      }
    }else{
      return;
    }
  }
}

复杂度：以数组访问次数计算

  • find：1
  • union：被合并分量只有一个触点时，2+N+1 = N+3；被合并分量有N-1个触点时，2+N+(N-1) = 2N+1。即，N+3 ~ 2N+1。
  • 需要N-1次操作，那么，至少需要(N-1)(N+3) ~ N^2^ 次数的数组访问。
  • 得，quick-union算法是平方级别的。

2.quick-union

用数组索引表示原始对象，对应值链接到所属分量(分量内，各触点使用通过值对应到另一个的索引连接–形成链)

==加快union；==

减慢find，要遍历当前触点到所属分量根触点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int find(int p){
  while(p != ids[p]){
    p = ids[p]							//复杂度增加
  }
  return p;
}

public void union(int p,int q){
  int pRoot = find(p);
  int qRoot = find(q);
  if(pRoot == qRoot) return;			//复杂度降低
  ids[pRoot] = qRoot;
  count--;
}

复杂度：以数组访问次数计算

  • find：最少1次，最多2*(N-1)+1=2N+1
  • union：2*(2N+1) ~ N；极端情况下，输入(0,1),(0,2)…… 2(1+2+3+…+N) ~ N^2^
  • 复杂度受输入影响较大

3.weighted quick-union

以两个数组表示，一个存储原始对象及所属链；另一个存储链的大小。

促使长度小的链，链接到长度大的链上。降低了树的高度，==解决了quick-union中极端情况下复杂度大的问题。==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private int[] ids;
private int[] sz;

private int find(int p){
  while(p != ids[p]){
    p = ids[p]
  } 
  return p;  
}

public void union(int p,int q){
  int pRoot = find(p);
  int qRoot = find(q);
  if(pRoot == qRoot) return;
  if(sz[pRoot] > sz[qRoot]){			//增加操作数，降低触点深度，提高find效率
    ids[qRoot] = pRoot;
    sz[pRoot] += sz[qRoot];
  }else{
    ids[pRoot] = qRoot;
    sz[qRoot] += sz[pRoot];
  }
  count--;
}