0

我有一个 N*N 布尔对称矩阵来显示每个元素的关系。

例如矩阵

1 0 1 
0 1 1
1 1 1

表示元素 1 与 1、3 有关系；元素 2 与 2,3 等有关系。

现在我想对元素进行聚类，因为矩阵大小很大（N=9000），我不想使用三层循环，而是想使用联合查找算法。

int labels[N];

static int find(int u){
    return u == labels[u] ? u : labels[u] = find(labels[u]);
}

static void myunion(int u,int v){
    labels[find(v)] = find(u); // the value of v is always larger than u
}

对于执行代码：

for(int i=0;i<size;i++){
    for{int j=i+1;j<size;j++){
        if(matrix[i][j]==1){
            myunion(i,j);// the value of j is always larger than i
        }
    }
}

问题是，我想始终使用最小的索引作为集群标签，但有时我的代码没有使用正确的标签。

例如，元素 2、3、100 是相关的。我希望集群有标签 2，但我得到标签 100 的结果。谁能告诉我我的逻辑错误？

我不确定是否

int pv = find(v);
int pu = find(u);

if(labels[pv]>=labels[pu]){
    labels[pv] = labels[pu];
}
else{
    labels[pu] = labels[pv];
}

工作，因为我担心如果，例如，{1,2,3}->label 1 ;{4,6}->label 4 当我调用 union(3,4) 时，labels[6] 也会是修改为1？

4

0 回答 0