title: My Prim's Algorithm (MST) runs much faster in a matrix than in a list
body: <p>I have some trouble implementing Prim's algorithm for finding Minimum Spanning Tree in a graph. 
  1. I generate an adjacency matrix, and run the algorithm to work on this matrix. The code:</p>
  
  <pre><code>void Graph::Prim(){
      int i=,j;
      int x=0,y=0,min,count=0;
      bool* visited=new bool[this-&gt;vertices_number]; // array of visited vertices
  
      for (int a=0;a&lt;this-&gt;vertices_number;a++)
          visited[a]=false;
  
      visited[0]=true; // checking the first vertex (start looking here)
  
      while(count &lt; this-&gt;vertices_number-1){
      min=INFINITY; //defined in header (large int)
          for (int i=0;i&lt;this-&gt;vertices_number;i++){              
              if (visited[i]==true){                              // looking for minimum-weight edge in all visited vertices
                  for(j=0;j&lt;this-&gt;vertices_number;j++){           //looking in one column
                      if (this-&gt;AdjacencyMatrix[i][j]&lt;min &amp;&amp; this-&gt;AdjacencyMatrix[i][j]&gt;0 &amp;&amp; visited[j]==false){ 
                      /* looking for lowest-weight edge which isn't already connected to the tree and isn't 0*/
                          min=AdjacencyMatrix[i][j]; //value
                          x=i;                        //row
                          y=j;                        //column
                      }
                  }
              }
          }
          visited[y]=true; //  added vertex
      //  cout &lt;&lt; x &lt;&lt; "--&gt;" &lt;&lt; y &lt;&lt; " : (" &lt;&lt; min &lt;&lt; ")"&lt;&lt;endl;
          count++; // visited vertex
      }
  }
  </code></pre>
  
  <p>Then, I want to do the same, but using an array of lists containing links. </p>
  
  <pre><code>class Link
  {
  public:
  int destination;
  int weight;
  ...
  };  
  </code></pre>
  
  <p>So I create an adjacency list:</p>
  
  <pre><code>list&lt;Link&gt; *AdjacencyList;
  AdjacencyList=new list&lt;Link&gt;[vertices_number];
  </code></pre>
  
  <p>So in the end the whole list is filled, ex. if vertex 0 and 4 are connected and the weight of connection is 7, AdjacencyList[0] contains Link with destination=4 and weight=7.</p>
  
  <p>I modified only the main loop of the algorithm, so now it uses iterator to find what it needs:</p>
  
  <pre><code>    if (visited[i]==true){ 
          for(list&lt;Link&gt;::iterator it = AdjacencyList[i].begin(); it != AdjacencyList[i].end(); it++){
              if ( visited[it-&gt;destination]==false &amp;&amp; it-&gt;weight &lt; min){
                  x=i;
                  y=it-&gt;destination;
                  min=it-&gt;weight;
  </code></pre>
  
  <p>The algorithms are able to find the same MST with no problems, the only thing is, the one which works on matrix is much faster, which is very surprising to me. For example, in a 80000 edges graph (random), while using matrix, the tree is found in miliseconds, but using list: whole second. Can anybody help me with this, or give a hint how to make this code more effective?</p>