title: Do I have to use a Union Find data structure when implementing Kruskal's algoithm?
body: <p>From what I've read about Kruskal's algorithm, it seems like we have to use a union find data structure. But why can't I just use an array of booleans which indicate whether a particular vertex has been added to the MST and just check that both vertices of an edge are have not been added to the MST instead? I.e. something like this (this is Java-like but is pseudocode-ish so it probably won't compile):</p>
  
  <pre><code>public Queue&lt;Edge&gt; getMST(Graph graph) {
    boolean[] visited = new boolean[graph.numVertices()];
    PriorityQueue&lt;Edge&gt; pq = new PriorityQueue&lt;&gt;();
    Queue&lt;Edge&gt; mstPath = new Queue&lt;&gt;();
    pq.addAll(graph.edges());
    while(mstPath.size() &lt; graph.numVertices() - 1 &amp;&amp; pq.isNotEmpty()) {
      Edge curr = pq.getMin();
      if (visited[curr.to] &amp;&amp; visited[curr.from]) continue; // ignore because both vertices of this edge are in MST
      mstPath.add(curr);
      visited[curr.to] = true;
      visited[curr.from] = true;
    }
    return mstPath;
  }
  </code></pre>
  
  <p>So why should I use a Union Find data structure? Won't the above work and be correct?</p>