Kibogozó

A Kibogozó (angolul untangled) készségfejlesztő játék lényege, hogy a felületen lévő pontokat úgy kell átrendezni, hogy egy vonaluk se keresztezze a másikat. Mintha gumiszalagok lennének a pontok között, vagy gráfok lennének.

Változatai

• Egy pályás alap változat: Untangle / kibogozó

• Gyakorló változat, néhány rögzített ponttal: Dont cross the line / ne keresztezd a vonalat

• Haladó változat: Brain stars / Elme csillagok

Gráfelméleti alapok

• Egy struktúra lehet összefüggő vagy több egységre bomló
• Ha egy rendszert áttekintéséhez rendezzük, az "kifeszítés"
• Az elemek vagy csomópontok kapcsolati hálózata a topológia
• Ha van egy jól meghatározható alap vagy kiindulópont, amihez minden kapcsolódik, akkor az egy Fa-gráf
• Lehetséges olyan kapcsolat, amely csak egy irányú
• Egy struktúra annál bonyolultabb, minél több elágazással rendelkező csomópontok vannak.
• A kapcsolatokat lehet mélységében feltárni DFS (Depth First Search, magyarulMélységi keresés) vagy BFS (Szélességi keresés)
  • Mélységi - gyors: az útvonalat megjegyezve addig haladok előre, amíg lehetséges, ha elakadok, csak az előző elágazásig megyek vissza, akkor próbálok másik utat
  • Szélességi - alapos: Amikor a kiindulóponttól minden utat végigpróbálok, és csak akkor megyek tovább, ha az adot pontban mindent felderítettem.
• A DFS algoritmus