Please enable JavaScript.

Coggle requires JavaScript to display documents.

9. Grafy (Typy grafů (stromy (typy (binomiální halda (navíc rychlé spojení…

- - - - isomorfismus
    - - n-ární strom
        
        úplný
      - uspořádaný strom
      - binární strom
      - binární halda
        
        mazání vrcholu
      - binomiální halda
        
        navíc rychlé spojení (konst. čas)
        
        tam, kde je třeba rychle MIN a MERGE
        
        např.: Dijkstrův alg.
        
        binom. strom řádu k
      - BVS
        
        binární strom
        
        nad úplně uspoř. množinou klíčů (N, <=)
        
        vyhledání vrcholu O(log n) - vyvážený
      - AVL strom
        
        BVS
        
        hloubka L a P podstromu libov. uzlu se liší o 1
        
        přidání/odebrání --> rotace
      - Č/Č strom
        
        BVS
        
        každý uzel Č/Č
        
        kořen černý
        
        červený --> černý
        
        = černých
        
        co nejmenší černá hloubka
      - B-strom
        
        vyvážený
        
        vyhledávání/odstraň. - log. čas
        
        řádu n
        
        využ.: přístupy do sekundární paměti
- - - - všechny seznamy za sebou
      - indexy počátků vrcholů
      - multigraf: násobné hrany
- - - - prázdný zásobník + pole předchůdců (null), uzly FRESH
      - vlož vrchol v na zásobník --> OPEN
        
        i. vrchol v
        
        ii. v - hledaný --> vrať
        
        iiia. v má nenavštíveného potomka (FRESH) vp
        
        vlož vp na zásobník, nastav OPEN
        
        nastav předchůdce vp jako v
        
        rekursivně k 1.
        
        iiib. jinak vyber vrchol v ze sásobníku + nastav CLOSE
    - - FRESH
      - OPEN (po nalezení)
      - CLOSED
    - - hledání vrcholu v grafu
      - topologické uspoř. uzlů grafu (CLOSED --> do zásobníku)
      - nalezení silných komponent - test souvisl. (po 1. průchodu obrátíme orientaci + znovu)
      - zjištění acykličnosti
  - - - FRESH
      - OPEN
      - CLOSED
    - - prázdná fronta, pole vzdáleností od kořene (vše nekonečno), kořen (0), pole předchůzců (null)
      - vlož do fronty výchozí vrchol v - OPEN
      - dokud je ve frontě vrchol
        
        i. vyjmi vrchol v
        
        ii. pokdu je v hledané, vrať
        
        iiia. pokud má v nenavštívené potomky
        
        vlož je do fronty + nastav OPEN
        
        zvyš jim vzdálenost od poč. o 1
        
        nastav jim jako předchůdce v
        
        iiib. jinak nastav v CLOSE
    - - hledání vrcholu
      - hledání nejkratší cesty
  - - - zpracovávané
      - zpracované
      - aktivní (připravené)
      - spící