algorithmgraphunion-find

Understanding union find

I read the wiki page and don't understand why it matters to append a smaller list to a larger one.

Here is that part of the algorithm from the wiki page:

Suppose you have a collection of lists and each node of each list contains an object, the name of the list to which it belongs, and the number of elements in that list. Also assume that the total number of elements in all lists is n (i.e. there are n elements overall). We wish to be able to merge any two of these lists, and update all of their nodes so that they still contain the name of the list to which they belong. The rule for merging the lists A and B is that if A is larger than B then merge the elements of B into A and update the elements that used to belong to B, and vice versa.

Solution

  • Union-Find is just a way for you to keep who is the "leader" of some set.

    For example, suppose you have 5 people A, B, C, D, E.

    Initially each one starts on its own set, so you can code it like this:

    for each person in people:
    parent[person] = person

    this way you can set every person to be the leader of its own set.

    this is what it should look like:

    {A}   {B}   {C}   {D}   {E}

    the first operation we need is to be able to find the leader of a set, and this operation is called find.

    then we fall into a property: a leader is someone who is its own parent.

    there are two possibilities, or the person is its own parent or it's not.

    if it is, then it is the leader of the set.

    if it is not, then we will ask the same thing (if it is its own parent) to its parent, and so it goes.

    you can code it like this:

    find_leader_of(person P){
    if(parent[P] == P) return P
    else return find_leader_of(parent[P])
}

    then we have the union operation, that's nothing more than turn 2 disjoints sets in one set only.

    suppose you have this situation:

    {A, B}        {C, D}         {E}

    and you do union(B, D), then what happens?

    first you need to find the leader of both sets:

    fst_leader = find_leader_of(B)
snd_leader = find_leader_of(D)

    then you choose any of these leaders to be the leader of the other:

    parent[snd_leader] = fst_leader

    and this results in:

    union(person P1, person P2){
    fst_leader = find_leader_of(P!)
    snd_leader = find_leader_of(P2)
    parent[snd_leader] = fst_leader
}

    there are other approaches to improve union-find and other ways to choose who will be leader of who, but this is the basics you must understand in order to know what union-find is about.