Kruskals Algorithmus und disjunkte Datenstruktur:Benötige ich die folgenden zwei Codezeilen?

Question

Ich habe Kruskals Algorithmus in C++ unter Verwendung der Disjunktmengen-Datenstruktur gemäß Wikipedia wie folgt implementiert:

#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);
}

Meine Frage ist:Benötige ich diese beiden Codezeilen?Wenn ja, welche Bedeutung haben sie?

1. int px=findset(x),py=findset(y);in merge statt int px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]); in findSet anstelle von return findset(parent[x]);

Answer 1

1) findset(x) gibt den kanonischen Repräsentanten der Menge zurück, in der sich x befindet (die Wurzel seines Stammbaums).Sie benötigen dies, um vergleichen zu können, ob sich zwei Elemente in derselben Menge befinden oder nicht (sie haben denselben Vertreter). parent[x] gibt lediglich das übergeordnete Element von x im Baum zurück, das möglicherweise nicht die Wurzel ist.

1a) Sie haben vergessen zu testen, ob px und py identisch sind merge.

2) Es handelt sich um eine Optimierung, damit zukünftige Anrufe möglich sind findset wird schneller laufen.Wenn parent[x] Wird verwendet, um nach diesem Aufruf auf sein übergeordnetes Element zu verweisen, das auf die Wurzel des Baums seiner Menge zeigt parent[x] zeigt direkt auf die Wurzel.

Answer 2

1. Sie brauchen das, weil x.parent ist nicht unbedingt der Vertreter der Klasse, zu der er gehört x gehört, daher wäre der Algorithmus ohne ihn nicht korrekt.
2. Ohne die Zuweisung wäre der Algorithmus suboptimal.Dies ist das Pfadkomprimierung Optimierung, auch in der Wikipedia diskutiert.