Algorytm Prima- działa w O(n^2) dla listy/wektora i macierzy, dlaczego?

Cześć, mam problem z algorytmem Prima. Otóż niezależnie od implementacji (czy to dla listy (wektora), czy macierzy sąsiedztwa) dostaję kwadratową złożoność obliczeniową, a chciałbym uzyskać logarytmiczną dla listy sąsiedztwa. Dodatkowo, algorytm dla listy (wektora) wykonuje się dużo, dużo wolniej, choć też rośnie kwadratowo.
Kod dla macierzy sąsiedztwa:

void Graf::Prim(){
	int i=0,j=0,x=0,y=0,min,licznik=0;
	bool* odwiedzono=new bool[this->liczba_wierzcholkow]; //tablica odwiedzonych wierzcholkow
	for (int a=0;a<this->liczba_wierzcholkow;a++)
		odwiedzono[a]=false; // na razie żaden
	odwiedzono[0]=true; //zaznaczamy pierwszy

	while(licznik < this->liczba_wierzcholkow-1){ //dopoki nie odwiedzimy wszystkich
	min=INFINITY;
		for (int i=0;i<this->liczba_wierzcholkow;i++){ //przeszukujemy za kazdym razem wszystkie dołączone wierzchołki
			if (odwiedzono[i]==true){ // szukamy krawedzi wychodzacych z odwiedzonych juz wierzcholkow
				for(j=0;j<this->liczba_wierzcholkow;j++){//szukamy w całej kolumnie najmniejszej wartosci
					if (this->MacierzSasiedztwa[i][j]<min && this->MacierzSasiedztwa[i][j]>0 && odwiedzono[j]==false){ 
				    /* szukamy krawedzi ktora ma minimalną ale różną od 0 wartość i nie łączy się z odwiedzonym już wierzchołkiem*/

						min=MacierzSasiedztwa[i][j]; //wartosc
						x=i;						//wiersz
						y=j;						//kolumna
					}
				}
			}
		}
		odwiedzono[y]=true; // wierzcholek y jest dolaczony do drzewa
		licznik++; // odwiedzilismy wierzcholek
	}
} 

Natomiast następnie tworzę tablicę wektorów połączeń (połączenie to wierzchołek końcowy i waga), czyli jeśli wierzchołek 0 jest połączony z 2 krawędzią o wadze 7, to ListaSasiedztwa[0] zawiera obiekt Polaczenie o wartosciach 2 i 7.

 
vector<Polaczenie> *ListaSasiedztwa;
ListaSasiedztwa=new vector<Polaczenie> [this->liczba_wierzcholkow];

class Polaczenie
{
public:
int cel;
int waga;
	...
}

Natomiast w algorytmie zamieniam tylko tą wewnętrzną pętle aby pracowała na iteratorze.

 				for(vector<Polaczenie>::iterator it = ListaSasiedztwa[i].begin(); it != ListaSasiedztwa[i].end(); it++){
					if ( odwiedzono[it->cel]==false && it->waga < min){
						x=i;
						y=it->cel;
						min=it->waga;
					}

Proszę o jakieś wskazówki.

Jak jedziesz 2 razy forem po tablicy wierzchołków to będzie przynajmniej O(n^2) + jeszcze ten while (mogę się mylić)

http://pl.wikipedia.org/wiki/Algorytm_Prima zaimplementuj ten z wiki na kolejce priorytetowej