4.6. Implementing Kruskal's Algorithm: The Union-Find Data Structure

• The basic idea behind the algorithm is that the graph in question has a fixed population of nodes
• And the graphs grows over time by inserting edges between certain pairs of nodes.
• Goal: Maintain a set of connected components of the graph being processed throughout the whole operation
• With this algorithm, we develop a data structure called the Union-Find structure
• The Union-Find data structure stores a representation of the components in a way that supports fast searching and updating
• This data structure is used to efficiently implement Kruskal's Algorithm
  

As each edge e = (u,w) is considered

Find the connected components containing v and w.

If these components are different:

Then there is no path from v to w, so e should be added to the structure

Elif they're the same:

Then there's a path from v to w, so e should be omitted.