c++ - My Prim's Algorithm (MST) runs much faster in a matrix than in a list -

i have trouble implementing prim's algorithm finding minimum spanning tree in graph. 1. generate adjacency matrix, , run algorithm work on matrix. code:

void graph::prim(){     int i=,j;     int x=0,y=0,min,count=0;     bool* visited=new bool[this->vertices_number]; // array of visited vertices      (int a=0;a<this->vertices_number;a++)         visited[a]=false;      visited[0]=true; // checking first vertex (start looking here)      while(count < this->vertices_number-1){     min=infinity; //defined in header (large int)         (int i=0;i<this->vertices_number;i++){                           if (visited[i]==true){                              // looking minimum-weight edge in visited vertices                 for(j=0;j<this->vertices_number;j++){           //looking in 1 column                     if (this->adjacencymatrix[i][j]<min && this->adjacencymatrix[i][j]>0 && visited[j]==false){                      /* looking lowest-weight edge isn't connected tree , isn't 0*/                         min=adjacencymatrix[i][j]; //value                         x=i;                        //row                         y=j;                        //column                     }                 }             }         }         visited[y]=true; //  added vertex     //  cout << x << "-->" << y << " : (" << min << ")"<<endl;         count++; // visited vertex     } } 

then, want same, using array of lists containing links.

class link { public: int destination; int weight; ... };   

so create adjacency list:

list<link> *adjacencylist; adjacencylist=new list<link>[vertices_number]; 

so in end whole list filled, ex. if vertex 0 , 4 connected , weight of connection 7, adjacencylist[0] contains link destination=4 , weight=7.

i modified main loop of algorithm, uses iterator find needs:

    if (visited[i]==true){          for(list<link>::iterator = adjacencylist[i].begin(); != adjacencylist[i].end(); it++){             if ( visited[it->destination]==false && it->weight < min){                 x=i;                 y=it->destination;                 min=it->weight; 

the algorithms able find same mst no problems, thing is, 1 works on matrix faster, surprising me. example, in 80000 edges graph (random), while using matrix, tree found in miliseconds, using list: whole second. can me this, or give hint how make code more effective?

i believe implementation using array faster implementation using lists because provides better memory locality, i.e. more friendly cache.