Minimalne drzewa rozpinające (projekt)

Spis treści

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 tablicy indeksowanej wierzchołkami jako kolejki priorytetowej.

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

Algorytm Prima używający 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.5)

Implementacja używająca drzewiastych 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

  • Zilustrować działanie zaimplementowanego algorytmu na zadanym grafie. Które krawędzie zostaną dodane do budowanego drzewa i w jakiej kolejności?
  • Jaka jest złożoność czasowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to opowiadają.
  • Jaka jest złożoność pamięciowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie gdzie alokowana jest pamięć (w jakiej ilości?).
  • Co to jest minimalne drzewo rozpinające? Co to jest drzewo? Co to znaczy, że jest ono minimalne? I co oznacza, że jest rozpinające?
  • Zaimplementowany algorytm (Prima lub Kruskala) jest przykładem algorytmu zachłannego. Co to jest algorytm zachłanny? Na jakiej zasadzie działa?

Dla wariantu używającego kopca binarnego

  • Co to jest kopiec binarny? Opisać tzw. warunek kopca, czyli zależność zachodzącą pomiędzy każdym węzłem i jego synami.
  • Dla zadanego kopca, zilustrować działanie wskazanej operacji: dodawania nowego elementu, usuwania korzenia, zmiany priorytetu.
  • Jaka jest czasowa złożoność poszczególnych operacji działających na kopcu?

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

  • Jak reprezentowane są zbiory rozłączne?
  • Zilustrować działanie wskazanej operacji na zbiorach rozłącznych: znajdywania korzenia/reprezentanta (z kompresją ścieżki), sprawdzenia czy dwa elementy należą do tego samego zbioru, złączenia dwóch zbiorów (z zaimplemtowaną w programie heurystyką podpinania: niższego drzewa do wyższego albo mniejszego do większego).
  • Jaka jest czasowa złożoność poszczególnych operacji działających na zbiorach rozłącznych?
Piotr Beling
Piotr Beling
adiunkt

Moje główne zaintersowania naukowe obejmują sztuczną inteligencję i teorię gier.