连通性

假设给定整数对的一个序列，其中每个整数表示某种类型的一个对象，用p-q表示“p连接到q”。假设“连通”关系是可以传递的：也就是说如果p和q之间连通，q和r之间连通，那么p和r之间也连通。我们的目标是写一个过滤集合中无关对的程序。

快速查找算法

求解N个对象的连通性问题，如果执行M次合并操作，至少需要执行M*N条指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#define N 10
main(){
    int i, p, q, t, id[N];
    for(i=0; i<N; i++){
        id[i] = i;
    }
    while(scanf("%d-%d", &p, &q) == 2){
        if(id[p] == id[q]){
            continue;
        }
        for(i=0, t=id[p]; i<N; i++){
            if(t == id[i]){
                id[i] = id[q];
            }
        }
        printf("%d-%d\n", p, q);
    }
}

输入	0	1	2	3	4	5	6	7	8	9	输出

快速合并算法

对于M>N，快速合并算法求解N个对象、M个对象的连通问题需要执行M*N/2条指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define N 10
main(){
    int i, j, p, q, id[N];
    for(i=0; i<N; i++){
        id[i] = i;
    }
    while(scanf("%d-%d", &p, &q) == 2){
        for(i=id[p]; i!=id[i]; i=id[i]);
        for(j=id[q]; j!=id[j]; j=id[j]);
        if (i == j) {
            continue;
        }
        id[i] = j;
        printf("%d-%d\n", p, q);
    }
}

输入	0	1	2	3	4	5	6	7	8	9	输出

加权快速合并算法

对于N个对象，加权快速合并算法判定其中的两个对象是否是连通的，至多需要遍历2lgN个指针。

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
#include <stdio.h>
#define N 10
main(){
    int i, j, p, q, id[N], sz[N];
    for(i=0; i<N; i++){
        id[i] = i;
        sz[i] = 1;
    }
    while(scanf("%d-%d", &p, &q) == 2){
        for(i=id[p]; i!=id[i]; i=id[i]);
        for(j=id[q]; j!=id[j]; j=id[j]);
        if (i == j) {
            continue;
        }
        if(sz[i] > sz[j]){
            id[j] = i;
            sz[i] += sz[j];
        }
        else{
            id[i] = j;
            sz[j] += sz[i];
        }
        printf("%d-%d\n", p, q);
    }
}

输入	0	1	2	3	4	5	6	7	8	9	输出