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 に答える