2

次のようなウィキペディアによる素集合データ構造を使用して、クラスカルのアルゴリズムをC++で実装しました。

#include <stdio.h>
#include <algorithm>
#define MAX_EDGES 10000000
#define MAX_VERTICES 200001
using namespace std;
int num_edges,num_vertices;
int total_cost=0;

struct edge{
    int v1,v2;
    int cost;
};

struct comp{
    bool operator()(const edge& e1,const edge& e2){
        return e1.cost<e2.cost;
    }
};

edge edges[MAX_EDGES];
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];

int findset(int x){
    if(x!=parent[x]){
        parent[x]=findset(parent[x]);
    }
    return parent[x];
}

void merge(int x,int y){
    int px=findset(x),py=findset(y);
    if(rank[px]>rank[py]){
        parent[py]=px;
    }else{
        parent[px]=py;
    }
    if(rank[px]==rank[py]){
        ++rank[py];
    }
}

int main(){
    FILE* in=fopen("input","r");
    FILE* out=fopen("output","w");
    fscanf(in,"%d %d\n",&num_vertices,&num_edges);
    for(int i=1;i<=num_vertices;++i){
        parent[i]=i;
        rank[i]=0;
    }
    for(int i=0;i<num_edges;++i){
        fscanf(in,"%d %d %d\n",&edges[i].v1,&edges[i].v2,&edges[i].cost);
    }
    sort(edges,edges+num_edges,comp());
    for(int i=0;i<num_edges;++i){
        int s1=findset(edges[i].v1),s2=findset(edges[i].v2);
        if(s1!=s2){
            merge(s1,s2);
            total_cost+=edges[i].cost;
        }
    }
    fprintf(out,"%d\n",total_cost);
}

私の質問は次のとおりです。これらの2行のコードが必要ですか？もしそうなら、彼らの重要性は何ですか？

  1. int px=findset(x),py=findset(y); 代わりにマージでint px=parent[x],py=parent[y];
  2. parent[x]=findset(parent[x]);の代わりにfindsetでreturn findset(parent[x]);
4

2 に答える 2

2

1）findset(x)xが含まれるセット（その祖先ツリーのルート）の正規の代表を返します。これは、2つの要素が同じセットにあるかどうか（同じ代​​表を持つ）を比較できるようにするために必要ですparent[x]。ツリー内のxの親を返すだけで、ルートではない可能性があります。

1a）でpxとpyが同一であるかどうかをテストするのを忘れましたmerge。

2）これは、への将来の呼び出しがより高速に実行されるように最適化されていfindsetます。parent[x]セットのツリーのルートを指している親を指すために使用される場合、この呼び出しの後parent[x]、ルートを直接指します。

于 2011-03-26T12:43:20.843 に答える
1
  1. x.parentが属するクラスの代表である必要はないため、これが必要です。これxがないと、アルゴリズムは正しくありません。
  2. 割り当てがないと、アルゴリズムは最適ではなくなります。これはパス圧縮の最適化であり、ウィキペディアでも説明されています。
于 2011-03-26T12:40:55.267 に答える