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.
No ale tutaj mam walsnie ten problem z upakowanie grafu do kopca.
Zakładam, że wprowadzam dane: węzeł, węzeł, krawędź(np. 1,2,2)itp. Czy łopatologicznie mógłbyś wyjaśnić jak to wprowadzić do kopca?
pozdrawiam