title: Prim is much slower than Kruskal's even in dense graphs
body: <p>I need to compare the difference in runtime between Kruskal's and Prim's algorithms in finding the MST in both sparse and dense graphs. For Kruskal's I use a find union structure, while for Prim's I use a bin heap (priority queue). This is my implementation:</p>
  <pre><code>std::vector&lt;bool&gt; visited(nNodes+1, false);
  std::vector&lt;int&gt; key(nNodes+1, std::numeric_limits&lt;int&gt;::max());
  std::vector&lt;int&gt; parent(nNodes+1);
  
  std::priority_queue&lt;std::pair&lt;int, int&gt;&gt; q;
  
  EdgeList mst_edges;
  q.push({ 0, 1 });
  
  while (!q.empty())
  {
      int a = q.top().second;
      q.pop();
      if(visited[a]) continue;
      visited[a] = true;
      for (const auto&amp; u : adjList[a])
      {
          int b = u.first, w = u.second;
          if (!visited[b]  &amp;&amp; key[b] &gt; w)
          {
              key[b] = w;
              parent[b] = a;
              q.push({ -w, b });
          }
      }
  }
  </code></pre>
  <p>This is supposed to have complexity O(Vlog(V)+Elog(V)) = O(Elog(V)), which is identical to Kruskal's. I have read however that Prim's is faster for dense graphs, but in my tests it is always slower. What am I doing wrong?</p>