5. gyakorlat

ZH anyag

• AVL
• B+ fa
• Gráfok (strukis feladat)
• Szélességi bejárás
• Mélységi bejárás

Mélységi bejárás

STACK!

irányított gráf -> struktúrális jelleg (Rekurzió :letsgoooo:)

A gráfból "extractol ki" egy fát.

• A fa élei: fa-él
• A gráf többi éleit kategorizálja:
  • vissza-él
    • Olyan élbe megy, amit már elkezdtünk feldolgozni, de nem fejeztük be
    • "\((u,v)\) vissza-él esetén \(v\) az \(u\) őse"
  • Előre-él
    • Olyan élbe megy, amit a jelenlegi csúcs után dolgoztunk fel
    • "\((u,v)\) előre-él esetén \(v\) az \(u\) leszármazottja, de \((u,v)\) nem fa-él"
  • kereszt-él
    • Olyan élbe megy, amit a jelenlegi csúcs előtt dolgoztunk fel
    • "\((u,v)\) kereszt-él ha \(u\) és \(v\) egy mélységi fa két külön ágán vannak, vagy két külön mélységi fában"