Minimalne drzewa rozpinające (projekt)


Warianty

Należy zaimplementować jeden z niżej wymienionych algorytmów znajdujących minimalne drzewo rozpinające oraz opanować (ze zrozumieniem) dotyczącą go teorię. Ocena zależy od wybranego wariantu i może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Algorytm Prima używający zwykłej tablicy (na ocenę 3.5)

Algorytm Prima używający jako kolejki priorytetowej tablicy indeksowanej wierzchołkami albo kopca binarnego z bibliotek języka.

Algorytm Prima używający kopca binarnego (na ocenę 4.5)

Algorytm Prima używający samodzielnie zaimplementowanego kopca binarnego jako kolejki priorytetowej.

Algorytm Kruskala z dowolną strukturą find-union (na ocenę 3)

Algorytm Kruskala z efektywną strukturą find-union (na ocenę 4)

Implementacja używająca drzewiastych, samodzielnie zaimplementowanych struktur do operacji na zbiorach rozłącznych.

Uwaga: Implementacja algorytmu Kruskala może używać sortowania z biblioteki języka. Należy jednak przeczytać w dokumentacji jaka jest złożoność tej operacji.

Budowanie labiryntu - opcjonalne rozszerzenie podwyższające ocenę o 1

Program używa zaimplementowano algorytmu do wygenerowania labiryntu.

Labirynt można narysować za pomocą ascii-art albo zapisać do pliku SVG. SVG to XMLowy format kodujący grafikę wektorową, który można otworzyć przeglądarką internetową. Do narysowania labiryntu wystarczy wiedza zawarta w tym przykładzie.

Przykładowe pytania sprawdzające

Dla wszystkich wariantów

Dla wariantu używającego kopca binarnego z bibliotek języka

Dla wariantu używającego własnej implementacji kopca binarnego

Dla wariantu używającego efektywnej (drzewiastej) implementacji find-union