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>

<p>Actually the running time of the algorithm is O(E log(V)).</p>

<p>The key to its performance lies on your point 4, more specifically, the implementation of determining for a light edge e = (a, b) if 'a' and 'b' belongs to the same set and, if not, performing the union of their respective sets.</p>

<p>For more clarifications on the topic I recommend you the book: "Introduction to Algoritms", from MIT Press, ISBN 0-262-03293-7, pag 561 (for the general topic of MST) and pag 568 (for Kruskal's Algorithm).
As it states, and I quote: </p>

<blockquote>
  <p>"The running time of Kruskalâs algorithm for a graph G = (V, E) depends
  on the implementation of the disjoint-set data structure. We shall assume the
  disjoint-set-forest implementation of Section 21.3 with the union-by-rank and
  path-compression heuristics, since it is the asymptotically fastest implementation
  known."</p>
</blockquote>

<p>Few lines later and with some simple "Time Complexity Theory" calculus, it proves its time complexity to be of O(E log(V)).</p>

python graph kruskals-algorithm