クラスカルのアルゴリズムと素集合のデータ構造:次の 2 行のコードが必要ですか?
-
12-11-2019 - |
質問
Wikipedia に従って、次のように素集合データ構造を使用して、クラスカルのアルゴリズムを 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 行のコードが必要ですか?もしそうなら、それらの重要性は何ですか?
int px=findset(x),py=findset(y);
代わりにマージでint px=parent[x],py=parent[y];
parent[x]=findset(parent[x]);
代わりにfindsetでreturn findset(parent[x]);
解決
1) findset(x)
x が含まれるセットの正規表現 (祖先ツリーのルート) を返します。これは、2 つの要素が同じセット内にあるかどうか (同じ代表値を持つかどうか) を比較できるようにするために必要です。 parent[x]
ツリー内の x の親を返すだけですが、これはルートではない可能性があります。
1a) px と py が同一であるかどうかをテストするのを忘れました。 merge
.
2) これは最適化であり、将来的には findset
より速く実行されます。もし parent[x]
この呼び出しの後、そのセットのツリーのルートを指す親を指していました。 parent[x]
ルートを直接指します。
他のヒント
- これが必要な理由は、
x.parent
必ずしも所属するクラスの代表である必要はないx
に属しているため、それがなければアルゴリズムは正しくありません。 - 割り当てがなければ、アルゴリズムは最適とは言えません。これは パス圧縮 最適化については、Wikipedia でも説明されています。
所属していません StackOverflow