Алгоритм Краскала и структура данных с непересекающимся множеством:Нужны ли мне следующие две строки кода?
-
12-11-2019 - |
Вопрос
Я реализовал алгоритм Крускала на 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);
}
Мой вопрос:Нужны ли мне эти две строки кода?Если да, то какова их важность?
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 (корень его родословного дерева).Это нужно вам, чтобы иметь возможность сравнивать, находятся ли два элемента в одном наборе или нет (у них один и тот же представитель), parent[x]
просто возвращает родителя x в дереве, который может не быть корнем.
1a) Вы забыли проверить идентичность px и py в merge
.
2) Это оптимизация, чтобы будущие вызовы findset
будет работать быстрее.Если parent[x]
используется для указания на своего родителя, который указывает на корень дерева своего набора, после этого вызова parent[x]
будет указывать непосредственно на корень.
Другие советы
- Вам это нужно, потому что
x.parent
не обязательно является представителем класса, к которомуx
принадлежит, поэтому без него алгоритм не будет корректным. - Без присваивания алгоритм был бы неоптимальным.Это сжатие пути оптимизация, также обсуждаемая в Википедии.