title: Understanding when to use Prim or Kruskal for Minimum Spanning Tree
body: <p>I'm trying to apply Prim's or Kruskal's algorithms to certain situations. I understand that Prim is used when graphs are dense (Example: as adjacency matrix with priority queue as unordered array would be good for a dense tree where <code>E = O(V^2)</code>. And Kruskal is used when graphs are sparse (Example: as adjacency list with fast sort where <code>E = O(V)</code>. What I'm unsure about is the in between. For example, a graph with a moderate number of edges such that </p>
  
  <pre><code>E = O(V log V)
  </code></pre>
  
  <p>Would this be Prim or Kruskal? I think it may be either one because Prim <code>O(E log V)</code> and Kruskal <code>O(E log E)</code> have similar time complexities.</p>