Witam! Napisałem taki oto algorytm Prima: http://pastebin.com/05tuFfkd
Napisałem go na podstawie działającej na 90% Dijkstry (wcześniej myślałem że 100 ale teraz sam nie wiem;/ ). Ponieważ tworzy on minimalne drzewo rozpinające każdy wierzchołek powinien mieć minimum jedną krawędź dla dowolnego grafu spójnego, jednak dla przykładu tak nie jest. Problemem jest to że pętla z warunkiem while(!kol.empty()) powinna wykonać się n razy, a wykonuje się tylko n-1 razy. Ma ktoś jakiś pomysł na naprawę tego?
Pzdr
0
0
Trzeba użyć debugger'a. Sprawdź w którym momencie przerywana jest pętla i dlaczego.
0
Znalazłem błąd. Okazuje się, że błąd tkwi w strukturze djcmp, z której operatora korzysta mój algorytm.
bool operator () (Ve* a, Ve* b)
{
//gdy jest: return a->odl < b->odl; dzieje się takie coś
return (a->odl == b->odl)?a < b : a->odl < b->odl;//gdy jest tak algorytm działa
}
Czy wiecie może dlaczego musi to być napisane tak jak wyżej, a nie tak jak w tym zakomentowanym?
0
Jaki błąd?
0
Ale jaki błąd otrzymujesz? Co widzisz przed oczami? Trzeba czytać.
0
Źle dodaje do seta. Np. gdy ma na set'cie elementy 0 i 1, to nie dodają się inne elementy, np.drugiego ani 3.
0
Mogę cię zapewnić, że set działa dobrze. Widocznie nie dochodzi do tego fragmentu gdzie ma dodać. Sprawdź debuggerem dlaczego.
0
sprawa jest prosta składowa "s" nie jest zainicjalizowana w konstruktorze.
0
Nie musi być zainicjowana w konstruktorze, gdyż s jest przypisywana wartość dopiero w Dijkstrze i dopiero potem z niej korzystam ;) Problemem był ten operator porównania.