Need some clarification on Kruskals and Union-Find
<p>Please help me fill any gaps in my knowledge(teaching myself):</p>

<p>So far I understand that given a graph of N vertices, and edges we want to form a MST that will have N-1 Edges</p>

<ol>
<li><p>We order the edges by their weight</p></li>
<li><p>We create a set of subsets where each vertice is given its own subset. So if we have {A,B,C,D} as our initial set of vertices, we now have {{A}, {B}, {C}, {D}}</p></li>
<li><p>We also create a set A that will hold the answer</p></li>
<li><p>We go down the list of ordered edges. We look at it's vertices, so V1 and V2. If they are in seperate subsets, we can join the two subsets, and add the edge into the set A that holds our edges. If they are in the same subset, we go to the next option (because its a cycle)</p></li>
<li><p>We continue this pattern until we reach the end of the Edge's list or we reach the Number of vertices - 1 for the length of our set A.</p></li>
</ol>

<p>If the above assertions are true, my following questions regard the implementation:</p>

<p>If we use a list[] to hold the subsets of the set that contains the vertice:</p>

<p>subsets = [[1][2][3][4][5][6][7]]</p>

<p>and each edge is composed of needing to look for two subsets
so we need to find (6,7)</p>

<p>the result would be</p>

<p>my_path = [(6,7)] #holds all paths
subsets = [[1][2][3][4][5][6,7]]</p>

<p>wouldn't finding the subset in subsets be taking too long to be O(nlog(n))</p>

<p>Is there a better approach or am i doing this correctly?</p>

<blockquote>
  <p>wouldn't finding the subset in subsets be taking too long to be O(nlog(n))</p>
</blockquote>

<p>Yes</p>

<blockquote>
  <p>Is there a better approach or am i doing this correctly?</p>
</blockquote>

<p>The better approach is using <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests" rel="nofollow">Disjoint Set Forest</a> data structure with <em>Union by Rank</em> technique. Applying this technique yields a worst-case running-time of O(log n) for the Union or Find operation</p>

python graph kruskals-algorithm