Witam wszystkich,
Mam za zadanie napisac programik wyznaczający minimalnege drzewo rozpinajace dla zadanego grafu metoda Kruskala z zastosowaniem kopca binarnego.
O ile algorytm Kruskala rozumiem dobrze, to mam problem z kopcem binarnym(rowniez w teorii znam). Jak zaimplementowac ten kopiec to mojego zadania?
Oczywiście nie oczekuję gotowego programu, ale będę wdzięczny za jakieś podpowiedzi które mnie naprowadzą:)
Implementacja kopca będzie klasyczna. Nie musisz nic zmieniać. Można równie dobrze wykorzystać priority_queue z STL-a.
Co do użycia to na początku pakujesz wszystkie krawędzie grafu do kopca, a później wykonujesz wielokrotnie deletemin.
Szczerze mówiąc nie słyszałem jeszcze o użyciu kopca w tym algorytmie. Wystarcza zwykłe sortowanie + unionfind.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.