Witam, piszę projekt, w którym mam zaimplementować algorytm Kruskala. Treść algorytmu znalazłem na wiki (http://pl.wikipedia.org/wiki/Algorytm_Kruskala) i zabrałem się za implementację. Problem pojawił się, gdy sprawdzałem to co mi algorytm zwrócił...
Oto mój kod:
void Drzewo::kruskal()
{
//każda galąź (wierzchołek) jest na początku oddzielnym drzewem
for (int i=0; i<this->IleWierzcholkow; i++)
this->Wierzcholki[i].Drzewo = i;
//zaznaczamy drogi jako nieużyte oraz inf taką,
//że jak na razie nie należą do mininalmego drzewa rozpinającego
for (vector<Droga>::size_type i = 0; i < Drogi.size(); ++i)
{
this->Drogi[i].NalezyDoMinimalnegoDrzewa = false;
this->Drogi[i].Uzyte = false;
}
Droga *akt = minimalnaDroga();
//każdy wierzchołek na początku należy do innego drzewa
for (int i=0; i<this->IleWierzcholkow; i++)
this->Wierzcholki[i].Drzewo = i;
while ((akt != 0) && (jednoDrzewo()))
{
akt->Uzyte = true;
if (this->Wierzcholki[akt->X].Drzewo != this->Wierzcholki[akt->Y].Drzewo)
{
akt->NalezyDoMinimalnegoDrzewa = true;
ustawInneDrzewo(Wierzcholki[akt->X].Drzewo, Wierzcholki[akt->Y].Drzewo);
}
akt = minimalnaDroga();
}
}
//sprawdza, czy wszystkie drzewa wierzchołki należą do jednego drzewa
bool Drzewo::jednoDrzewo()
{
int d = Wierzcholki[0].Drzewo;
for (int i=1; i<this->IleWierzcholkow; i++)
{
if (Wierzcholki[0].Drzewo != d)
return false;
}
return true;
}
//najkrótsza droga w grafie, nie należąca do drzewa oraz jeszcze nie odwiedzona (użyta)
Droga * Drzewo::minimalnaDroga()
{
Droga *minD = 0;
int minI = INT_MAX;
for (vector<Droga>::size_type i = 0; i < Drogi.size(); ++i)
if ((!Drogi[i].Uzyte) && (!Drogi[i].NalezyDoMinimalnegoDrzewa))
if (Drogi[i].Waga<minI)
{
minI = Drogi[i].Waga;
minD = &Drogi[i];
}
return minD;
}
Mój problem pojawia się, gdy sprawdzam to na przykładzie, gdzie graf wygląda tak: http://img130.imageshack.us/img130/2678/zrzutekranua.png
natomiast mój program zwraca taki graf (niebieskie krawędzie "należą" do minimalnego drzewa): http://img130.imageshack.us/img130/9690/zrzutekranu1ao.png
czy mógłby mi ktoś powiedzieć gdzie mam szukać błędu? Nie chcę gotowego kodu a instrukcji, gdzie szukać pomyłki.
