Cvičenie č.5

Ciele
  1. ADT binárny strom (binary tree), implementácia pomocou poľa.
  2. Podľa pokynov upraviť/doplniť implementáciu.
  3. ADT graf (graph), implementácia s využitím incidenčnej matice.
  4. Podľa pokynov upraviť/doplniť implementáciu.
Úvod
    Náplňou cvičenia je implementácia abstraktných údajových typov (ADT) binárny strom (binary tree) a graf (graph).
Postup
  1. ADT binárny strom.
    • V rámci stromových údajových štruktúr významnú úlohu zohrávajú binárne stromy. Pre ADT binárny strom využijeme v rámci tohto cvičenia implementáciu pomocou (jedného) poľa.
    • Mapovanie vrcholu stromu na index poľa: ľavý potomok vrcholu na pozícii i sa nachádza na pozícii 2i, pravý na 2i+1. Koreň stromu je na prvej pozícii v poli.
    • Použitím poľa možno reprezentovať ľubovoľný binárny strom, pri reprezentácii úplného binárneho stromu je ale priestor využitý optimálne.
    • Často sú využívané aj iné reprezentácie, napr. s využitím smerníkov odkazujúcich na potomkov daného vrcholu.

    Príklad: Reprezentácia binárneho stromu s piatimi vrcholmi.

    Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

    Pripravený archív obsahuje tieto súbory:

    • fatal.h - definičný modul pre ošetrenie chýb.
    • tree_arr.h - definičný modul ADT binárny strom (prototypy operácií, údajové typy).
    • tree_arr.c - implementačný modul ADT binárny strom (implementácia operácií).
    • test.c - modul pre testovanie činnosti ADT binárny strom.

    Operácie pre ADT binárny strom:

    • CreateTree - vytvorí strom.
    • DisposeTree - odstráni, uvoľní pamäť.
    • MakeEmpty - vyprázdni strom (vrcholy inicializuje na hodnotu 0).
    • Insert - vloží prvok do stromu.
    • PrintTree - vypíše na obrazovku hodnoty priradené vrcholom stromu po jednotlivých úrovniach.

    Príklad: Označenie úrovní v strome s piatimi vrcholmi.

    Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
  2. Doplnenie/úprava implementácie.
    Úloha: Pridajte podporu operácie PrintRow, ktorá vypíše hodnoty vrcholov na zadanej úrovni stromu.
    Prototyp operácie PrintRow: 
    void PrintRow ( Tree T, int Level );
    Úloha: Pridajte podporu operácie PrintSubtree, ktorá vypíše hodnoty vrcholov podstromu, ktorého koreňom je prvok so zadaným indexom.
    Prototyp operácie PrintSubtree: 
    void PrintSubtree( Tree T, int Index );
    Poznámka: Pre overenie činnosti operácie doplňte aj modul pre testovanie.
  3. ADT graf.
    • Grafy sú ÚŠ často využívané na reprezentáciu relácií medzi objektmi.
    • Reprezentácia grafu s n vrcholmi - bežne matica s rozmerom n x n. Ak v grafe existuje hrana medzi vi a vj, potom prvok matice na riadku i a stĺpci j má hodnotu 1.
    • V prípade neorientovaného grafu s e hranami, príslušná incidenčná matica obsahuje 2e prvkov s hodnotou 1. V prípade orientovaného grafu s e hranami bude matica obsahovať iba e jednotiek.
    • Iným bežným spôsobom reprezentácie grafu je použitie zoznamu (s vrcholmi incidentnými s daným vrcholom) pre všetky vrcholy grafu.

    Príklad: Reprezentácia grafov incidenčnými maticami.

    Spôsoby systematického prechádzania grafom:

    • Prehľadávanie do hĺbky - navštevovanie vrcholov (hlbšie) pokiaľ je to možné (depth-first traversal).
    • Prehľadávanie do šírky (breadth-first traversal).
    Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.
    Poznámka: Pripravený archív obsahuje súbory fatal.h, graph.h, graph.c, test.c s obvyklým významom.

    Operácie pre ADT graf:

    • CreateGraph - vytvorí graf.
    • DisposeGraph - odstráni, uvoľní pamäť.
    • buildadjm - vytvorí incidenčnú maticu.
    • printadjm - vypíše incidenčnú maticu.
    • ClearVisited - vymaže záznamy o navštívených uzloch.
    • dfs - prehľadávanie grafu do hĺbky (depth first search).
    • dfsst - kostra grafu (spanning tree) získaná prehľadávaním do hĺbky.
    • bfs - prehľadávanie grafu do šírky (breadth first search).
    • bfsst - kostra grafu (spanning tree) získaná prehľadávaním do šírky.
    Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
  4. Doplnenie/úprava implementácie.
    Úloha: Nájdite chybu a opravte ju v implementácii operácie pre prehľadávanie grafu do hĺbky dfs. Operácia dfs pre svoju činnosť využíva rekurzívnu funkciu dfsr().
    Správna činnosť operácie (pre daný graf) je zachytená na obrázku:
    Úloha: Pridajte podporu operácie dfsst, ktorá vypíše hrany tvoriace kostru grafu (spanning tree) získanú prehľadávaním do hĺbky. V prípade, že zadaný graf nie je súvislý, vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do hĺbky (spanning forest).

    Prototyp operácie dfsst: 

    void dfsst(Graph G);
    Úloha: Vytvorte operáciu bfs realizujúcu prehľadávanie grafu do šírky. Implementujte operáciu bfsst, ktorá vypíše hrany tvoriace kostru grafu (spanning tree) získanú prehľadávaním do šírky. V prípade nesúvislého grafu vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do šírky (spanning forest).

    Prototypy operácií bfs a bfsst: 

                
void bfs(Graph G);
void bfsst(Graph G);
    Poznámka: Pre overenie činnosti operácií doplňte aj modul pre testovanie.
    Poznámka: Odstráňte z disku vami vytvorené projekty a súbory. Zanechajte vývojové prostredie v pôvodnom stave.
Doplňujúce úlohy
    Úloha: Implementujte operáciu na binárnom strome BuildHeap(), ktorá preusporiada prvky tak, aby tvorili haldu ((max) heap).
comments powered by Disqus