Union-Find ist nur eine Möglichkeit für Sie, wer ist der "Führer" eines Satzes.
Beispiel: Angenommen, Sie haben 5 Personen A, B, C, D, E.
zunächst jeder auf seinem eigenen Satz beginnt, so dass Sie es wie dieser Code:
for each person in people:
dad[person] = person
Auf diese Weise können Sie jede Person zum Anführer ihrer eigenen Gruppe machen.
das ist, was es aussehen sollte:
{A} {B} {C} {D} {E}
die erste Operation ist in der Lage den Führer eines Satzes zu finden, und dieser Vorgang genannt find ist wir brauchen.
dann fallen wir in eine Eigenschaft: ein Führer ist jemand, der sein eigener Vater ist.
gibt es zwei Möglichkeiten, oder die Person ist ihr eigener Vater oder es ist nicht.
Wenn es ist, dann ist es der Anführer des Satzes.
Wenn es nicht ist, dann werden wir das Gleiche (wenn es sein eigener Vater ist) nach seinem Vater fragen, und so geht es.
können Sie es wie folgt Code:
find_leader_of(person P){
if(dad[P] == P) return P
else return find_leader_of(dad[P])
}
dann haben wir die union Betrieb, das ist nichts anderes als nur gesetzt, in einem 2 disjoints Sätze drehen.
nehme an, Sie haben diese Situation:
{A, B} {C, D} {E}
und Sie tun union(B, D), was geschieht dann?
müssen Sie zuerst die Führer beider Sätze zu finden:
fst_leader = find_leader_of(B)
snd_leader = find_leader_of(D)
dann wählen Sie eines dieser Führer der Führer der anderen zu sein:
dad[snd_leader] = fst_leader
und dies führt zu:
union(person P1, person P2){
fst_leader = find_leader_of(P!)
snd_leader = find_leader_of(P2)
dad[snd_leader] = fst_leader
}
Es gibt andere Ansätze, um die gewerkschaftliche Suche zu verbessern und andere Wege zu wählen, wer der Anführer von wem ist, aber das sind die Grundlagen, die Sie verstehen müssen, um zu wissen, worum es beim Gewerkschaftsfund geht.