Algoritmo de Kruskal y estructura de datos de conjuntos disjuntos:¿Necesito las siguientes dos líneas de código?
-
12-11-2019 - |
Pregunta
Implementé el algoritmo de Kruskal en C++ usando la estructura de datos de conjuntos disjuntos según Wikipedia de esta manera:
#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);
}
Mi pregunta es:¿Necesito estas dos líneas de código?Si es así, ¿cuál es su importancia?
int px=findset(x),py=findset(y);
en fusionar en lugar deint px=parent[x],py=parent[y];
parent[x]=findset(parent[x]);
en findset en lugar dereturn findset(parent[x]);
Solución
1) findset(x)
devuelve el representante canónico del conjunto en el que se encuentra x (la raíz de su árbol de ascendencia).Necesitas esto para poder comparar si dos elementos están en el mismo conjunto o no (tienen el mismo representante), parent[x]
simplemente devuelve el padre de x en el árbol, que puede no ser la raíz.
1a) Olvidaste probar que px y py sean idénticos en merge
.
2) Es una optimización para que futuras llamadas a findset
correrá más rápido.Si parent[x]
solía apuntar a su padre que apuntaba a la raíz del árbol de su conjunto, después de esta llamada parent[x]
apuntará directamente a la raíz.
Otros consejos
- Necesitas esto porque
x.parent
no es necesariamente el representante de la clase a la que pertenecex
pertenece, por lo que el algoritmo no sería correcto sin él. - Sin la asignación, el algoritmo sería subóptimo.Este es el compresión de ruta optimización, también discutida en la Wikipedia.