接続性問題の改善アルゴリズム
17042 ワード
前の「接続性問題」ではこの問題を紹介しましたが、この章では上記の問題に対する改善を与え、コードの中で原理についてコメントしました.
加重高速合成アルゴリズム
パス圧縮アルゴリズム
加重高速合成アルゴリズム
1 /**
2 * @file weightedquickunion.c
3 * @brief
4 * ， ， ，
5 * 。 ，
6 * sz id[i]==i ，
7 * ， 。
8 * @date 2015-01-15
9 */
10 #include <stdio.h>
11 #define N 1000
12
13 int main(void)
14 {
15 int i, j, p, q;
16 int id[N], sz[N];
17 //
18 for (i = 0; i < N; i++)
19 {
20 id[i] = i;
21 sz[i] = 1;
22 }
23 //
24 while (scanf("%d-%d", &p, &q) == 2)
25 {
26 // p
27 for (i = p; i != id[i]; i = id[i]);
28 // q
29 for (j = q; j != id[j]; j = id[j]);
30 // p q ，
31 if (i == j) continue;
32 // ， p q
33 if (sz[i] < sz[j])
34 {//q
35 id[i] = j; // p q
36 sz[j] += sz[i];//q p
37 }
38 else
39 {//p
40 id[j] = i; // q p
41 sz[i] += sz[j];//p q
42 }
43 printf("New Pair: %d-%d
", p, q);
44 }
45
46 return 0;
47 }パス圧縮アルゴリズム
1 /**
2 * @file pathcompression.c
3 * @brief
4 * ， ， ，
5 * 。 ，
6 * sz id[i]==i ，
7 * ， 。
8 * @brief ： ， ，
9 * id 。 ， ，
10 * ， ， 。
11 * @brief ： 。
12 * @date 2015-01-15
13 */
14 #include <stdio.h>
15 #define N 1000
16 #if 0
17 #define PATH_COMPRESSION //
18 #else
19 #define EQUAL_PATHCOMPRESSION //
20 #endif // 0
21
22 int main(void)
23 {
24 int i, j, p, q, index;
25 int id[N], sz[N];
26 //
27 for (i = 0; i < N; i++)
28 {
29 id[i] = i;
30 sz[i] = 1;
31 }
32 //
33 while (scanf("%d-%d", &p, &q) == 2)
34 {
35 #ifdef EQUAL_PATHCOMPRESSION
36 // p
37 for (i = p; i != id[i]; i = id[i])
38 id[i] = id[id[i]];
39 // q
40 for (j = q; j != id[j]; j = id[j]);
41 id[j] = id[id[j]];
42 #else
43 // p
44 for (i = p; i != id[i]; i = id[i]);
45 // q
46 for (j = q; j != id[j]; j = id[j]);
47 #endif // EQUAL_PATHCOMPRESSION
48
49 // p q ，
50 if (i == j) continue;
51 // ， p q
52 if (sz[i] < sz[j])
53 {//q
54 id[i] = j; // p q
55 sz[j] += sz[i];//q p
56 #ifdef PATH_COMPRESSION
57 //
58 for (i = q; i != id[i];)
59 {
60 index = i; //
61 i = id[i]; //
62 id[index] = j; //
63 }
64 #endif // PATH_COMPRESSION
65 }
66 else
67 {//p
68 id[j] = i; // q p
69 sz[i] += sz[j];//p q
70 #ifdef PATH_COMPRESSION
71 //
72 for (j= p; j != id[j];)
73 {
74 index = j; //
75 j = id[j]; //
76 id[index] = i; //
77 }
78 #endif // PATH_COMPRESSION
79 }
80 printf("New Pair: %d-%d
", p, q);
81 }
82
83 return 0;
84 }