0

通常使用秩和路径压缩的启发式方法来实现快速的不相交集数据结构操作。不知何故，我发现按重量和路径压缩的启发式方法对我来说更明智。以下实现是否通过等级和路径压缩实现了与启发式方法相同的运行时间？

注意：结构节点中使用的排名是用词不当，它指的是孩子的数量而不是树的高度（排名一般意味着）

//using heuristics by weight and path compression to improve running time
typedef struct n{
    struct n *parent;
    int u,v,weight;
    int rank;        //if node is the parent, it keeps track of number of children. if not, it is -1.
}node;

node* MAKE(int u, int v, int weight)
{
    node *n=(node*)malloc(sizeof(node));
    n->parent=n;
    n->u=u;
    n->v=v;
    n->weight=weight;
    n->rank=0;
    return n;
}

node *FIND(node *n)
{
    if(n->parent==n)
        return n;
    n->parent=FIND(n->parent);
    return n->parent;
}

void MERGE(node *n1, node *n2)     //merge n1 and n2 and store in n1.
{
    assert(n1->rank!=-1);
    assert(n2->rank!=-1);
    if(n1->rank<n2->rank)
    {
        MERGE(n2,n1);
        return ;
    }
    n2->parent=n1;
    n1->rank=n1->rank+n2->rank+1;
    n2->rank=-1;
}
4

1 回答 1

2

你在你的结构中都使用weight了rank！如果weight你的意思是加权合并启发式，那通常rank是为了（rank我指的是你提到的树的高度，而不是孩子的数量）。

跟踪孩子的数量不会给您任何优化！因为复杂度Find是树的高度的函数，而不是我们的输入节点所在的树中的子节点数。

尽管您从路径压缩中受益。

于 2013-08-14T21:34:10.293 回答