c - Union Find - 快速查找

Question

我刚刚开始普林斯顿算法类(class)，并尝试用 C 语言实现一个非常基本的快速查找算法，如下 -

#include <stdio.h>

void find(int *, int, int);
void unite(int *, int, int);

int main() {
    int arr[10], i, n1, n2, opt;
    char ch;

    for (i = 0; i < 10; i++)
        arr[i] = i;

    do {
        printf("1. Find\n2. Union\n");
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d,%d", &n1, &n2);
            find(arr, n1, n2);
        }
        if (opt == 2) {
            scanf("%d,%d", &n1, &n2);
            unite(arr, n1, n2);
        }
        for (i = 0; i < 10; i++)
            printf("%d  ", arr[i]);
        printf("Continue? (Y/N)");
        getchar();
        scanf("%c", &ch);
    } while (ch == 'Y');
}

void find(int *id, int p, int q) {
    if ((*(id + p)) == (*(id + q)))
        printf("Connected\n");
}

void unite(int *id, int p, int q) {
    int i;
    for (i = 0; i < 10; i++) {
        if ((*(id + i)) == (*(id + p)))
            *(id + i) = *(id + q);
    }
}

程序没有按预期运行。当我尝试执行 union(4,3) 然后执行 union(3,8) 时，只有 arr[3] 更改其值而不是 arr[4]。另外，我不确定为什么我必须使用 getchar (没有它程序就一直结束)。

Answer 1

这一行:

if((*(id+i))==(*(id+p)))

相当于:

if (id[i] == id[p])

并用 p 的当前 id 来测试 i 的当前 id。

问题是 id[p] 可能已经更改为 id[q]!

因此，当你尝试将所有 3 变为 8 时，在我们将 arr[3] 更改为 8 后，从那时起我们只是将 8 更改为 8。

而是尝试存储 p 的当前 id，并对其进行测试:

void unite(int *id, int p, int q)
{
    int i;
    int id_to_change = id[p];
    for(i=0;i<10;i++)
    {
        if(id[i] == id_to_change)
            id[i] = id[q];
    }
}