Kruskal's algorithm explanation

Question

I was reading wikipeida and found Kruskal's Pseudocode as the following:

KRUSKAL(G):    
    foreach v ∈ G.V:    
        MAKE_SET(v)    
    G.E = sort(G.E)    
    i = 0    
    while (i != |V|-1):      
        pick the next (u, v) edge from sorted list of edges G.E        
        if (FIND_SET(u) != FIND_SET(v)):          
            UNION(u, v)        
            i = i + 1 

I'm not quiet sure what FIND_SET() does, and Wikipedia has the follow description:

if that edge connects two different trees, then add it to the forest, combining two trees into a single tree.

So I guess it checks if two different trees are connected, but what does this really mean?

Answer 1

Initially, each vertex is in a set all by itself: There is a singleton set {v} for every vertex v. In the pseudo-code, these sets are the result of make_set(v).

For a given vertex v, the function find_set(v) gives you the set containing v.

The algorithm merges sets iteratively, so if {u}, {v} are singleton sets initially and there is an edge (u, v), then the algorithm replaces the two sets by their union {u, v}. Now both find_set(u) and find_set(v) will return that set.

The algorithm terminates after you've added |V| - 1 non-trivial edges, which is precisely the number of edges in a tree.

Answer 2

FIND_SET(x) finds the set associated with edge x, so that the comparison:

FIND_SET(u) != FIND_SET(v)

Ensures that u and v are not connected to the same thing. A useful way of thinking about it is that it finds the "values" of u and v where the values are in themselves sets.

The part about merging the forests has nothing to do with FIND_SET, but rather the next line:

UNION(u,v)

Which merges the two sets.

Answer 3

The find_set() is a common operation of a kind of data structure known as Union-Find. The idea of this data structure is to have disjoint sets (of vertex in your example).

In this algorithm I think that each set represents vertex that are connected.

So when you call find_set() passing a vertex, you will receive the element that represents that set of connected verxtex.

Answer 4

find_set(u)!=find_set(v) 

signifies the basic property of spanning tree that is it does not make cycles.If they are equal then it shows there is a cycle in graph.

We basically make a forest (of minimum edge weights) through Kruskal algorithm and at each step checks whether it is making cycle or not.

Hope it helps :)