title: Prim's Algorithm C++
body: <p>I'm implementing a simple version of Prim's algorithm in C++ and having some difficulty translating the algorithm to work with my very basic graph implementation.</p>
  
  <p>I have a struct for edges as follows:</p>
  
  <pre><code>struct edge 
  {
      int src;
      int dest;
      int weight;
  };
  </code></pre>
  
  <p>I simply push the edges to a vector in the graph class. I'm not sure if this is the best way to implement Prim's but it seems to be optimal for my end result which is being able to simply print out the amount of vertices visitTed and the total weight of the minimal spanning tree.</p>
  
  <p>I think I understand the basic idea of Prim's but I have questions on a few points. All I'm asking for is a push in the right direction. Pseudocode specific to my usage would be ideal though.</p>
  
  <p>1) Pick a starting vertex</p>
  
  <p>2) In a while loop from the source vertex to all others, add the edge weights to a heap of some sort (this is confusing to me, some algorithms say to initialize to infinity but STL priority queue doesn't have a reserve method...)</p>
  
  <p>3) Get the lowest edge (pop from priority queue or in my poorly thought out implementation traverse the vector for the lowest value...)</p>
  
  <p>4) If the destination of the lowest value has been visited, throw that edge away and try the next. If not, add the edge to the minimum spanning tree and mark it visited.</p>
  
  <p>I don't have much code and am getting to a point of diminishing returns, so any advice is appreciated. Here's what I got:</p>
  
  <pre><code>vector&lt;edge&gt; graph::prims(int source, vector&lt;edge&gt; vt)
  {
      int current;
      vector&lt;bool&gt; visited(numVert, false);
      vector&lt;unsigned int&gt; minWeight;
      minWeight.reserve(numVert);
  
      // Intilize minWeight to a large number
      for(int j=0; j &lt; numEdges; j++)
      {
          minWeight[j] = 0xffffffff;
      }
  
      current = source; 
  
      // Will this even work? What if I pick the nth node...
      while (current &lt;= numEdges)
      {
          // This should add the edge weights to the current vertex 
          // to a vector so the minimum can be found
          for(int i = 0; i &lt; numVert; i++)
          {
              if(vt[i].src == current &amp;&amp; visted[i] == false)
              {
                  minWeight.push_back(vt[i].weight);
              }
          }
      }
  
      // Need to finish Prim's
  
  
      return vt;
  }
  </code></pre>
  
  <p>I've been trying to get code off the internet and modify all day and it got me nowhere. So I finally decided to attempt it myself. It's not much but this took me about two hours...</p>
  
  <p>My code can be found on <a href="https://drive.google.com/folderview?id=0B2h2H0IGYVFkbWFERnNtZHJrbnc&amp;usp=sharing" rel="nofollow">Google Drive</a>.</p>