前言

经过几天愉悦的学习,我终于对 查找-合并算法 有了初步的认识。
我来初步叙述这个算法所针对的问题。

现实

可以想象这样一个情景,在一个局域网内,有N台电脑。它们的编号分别是0 ~ N-1。编号1和编号2的电脑连通,编号2和编号3的电脑连通,则编号1和编号3的电脑通过这个网络就实现了互联。通过这些连通,就形成了一个网络。


数学抽象

在数学的角度看来,就是在解决集合的传递性。

  • p - q, q - r, p - r;

快速查找算法

算法的基础是一个整型数组, 初始化时数组元素的值等于本身。如果第p个元素与第q个元素相等,则P和q是连通的,否则执行合并操作,将所有等于第P个元素值的元素都置为第q个元素的值。。如果第p个元素与第q个元素相等,则P和q是连通的,否则执行合并操作,将所有等于第P个元素值的元素都置为第q个元素的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int p, q, temp, i;
int a[size];

for( i = 0 ; i < size; i ++){
a[i] = i;
}

while(scanf("%d%d", &p, &q) == 2){
if(a[p] == a[q]) continue;

for(i = 0, temp = a[p]; i < size; i++){
if(a[i] == temp)
a[i] = a[q];
}
}

快速合并算法

算法的基础也是一个整型数组,初始化时数组元素的值等于本身。p数组元素的根与q数组元素的根不同时,每次将下标为q的数组元素值,赋值给小标为p的数组元素。p数组元素的根与
q的数组元素根相同时,则继续获取p、q。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int p, q, i, j;
int a[size];

for( i = 0 ; i < size; i ++){
a[i] = i;
}

while(scanf("%d%d", &p, &q) == 2){
for(i = p; a[i] != i; i = a[i]); //追溯到p所在集合的根
for(j = q; a[j] != j; j = a[j]); //追溯到q所在集合的根

if(i == j) continue; //i, j相等则继续获取
a[i] = j;
}


加权快速合并算法

这个算法是在快速合并算法的基础上优化的。当快速合并算法遇到类似与1-2、2-3、3-4、4-5、5-6、6-7、7-8、8-9输入时,会形成一条直线的树,平均每个元素会经过n-1个指针才能到达根指针。
为了解决这种最坏的情况。我们在合并是进行了一个优化,初始化时定义了一个关于每个节点上所带有节点数量的数组,初始化都为1。在合并是将节点数少的树并归到节点数多的树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int p, q, i, j;
int a[size];

for(i = 0; i < size; i++){
a[i] = i, sz[i] = 1;
}

while(scanf("%d%d", &p, &q) == 2){
for(i = p; a[i] != i; i = a[i]); //追溯到p所在集合的根
for(j = q; a[j] != j; j = a[j]); //追溯到q所在集合的根

if(i == j) continue;

if(sz[i] > sz[j]){ //如果p所在树的节点数大于q所在数的节点数, 则将q连接到p,归并后节点数相加。
a[j] = i;
sz[i] += sz[j];
}else{
a[i] = j;
sz[j] += sz[i];
}

}


路径压缩加权快速合并算法

为了使算法可在线性时间内求解问题。理想情况下我们希望将所有节点都直接指向根节点,则对加权快速合并算法进行了优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int p, q, i , j;

for(i = 0; i < size; i++){
a[i] = i, sz[i] = 1;
}

while(scanf("%d%d", &p, &q) == 2){
for(i = p; a[i] != i; i = a[i]);
for(j = q; a[j] != j; j = a[j]);

if(i == j) continue;

if(sz[i] < sz[j]){
a[i] = j;
sz[j] += sz[i];
}else{
a[j] = i;
sz[i] += sz[i];
}

for(i = 0; i < size; i++){
a[i] = a[a[i]];
}
}

等分路径压缩加权快速合并算法

等分了遍历的任何路径的长度,树几乎完全是扁平的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int p, q, i , j;

for(i = 0; i < size; i++){
a[i] = i, sz[i] = 1;
}

while(scanf("%d%d", &p, &q) == 2){
for(i = p; a[i] != i; i = a[i])
a[i] = a[a[i]];
for(j = q; a[j] != j; j = a[j])
a[j] = a[a[j]];

if(i == j) continue;

if(sz[i] < sz[j]){
a[i] = j;
sz[j] += sz[i];
}else{
a[j] = i;
sz[i] += sz[i];
}
}

感谢从这些网络链接和书籍中获得帮助。
http://blog.csdn.net/u010707039/article/details/51954033
《算法:c语言实现》

留言

⬆︎TOP