Gyakorlati alapok III.

Az adatszerkezetek - Gráf és hálózat

A gráf tulajdonságai hasonlóak a fához, szintén 2 elemből állnak:

• csomópont, csúcs - dolgok, entitások - legtöbbször körök jelképezik,

• él - a rajtuk értelmezett összeköttetések, kapcsolatok - legtöbbször nyilak jelképezik.

A gráf és hálózat, valamint a faszerkezet között annyi a különbség, hogy az előbbiek esetében 2 csomópont között lehet 2 irányú is a kapcsolat. (Emlékezzünk vissza, hogy fa esetében a kapcsolat csakis 1 irányú.) A gráf és hálózat tehát már hálós adatszerkezetet alkot.

Fajtái:

• címkézett gráf - a gráf csomópontjai egyedi azonosítóval rendelkeznek (például számozás), ám ez sok esetben funkcionálisan felesleges (címkézetlen gráf),

Forrás - Source: www.szit.hu

• irányított gráf - élei irányítottak, ezt a csomópont felé mutató nyilak reprezentálják,

Forrás - Source: www.szit.hu

• hálózat - ha a kapcsolatokhoz valamilyen mérőszám is tartozik.

A hálós adatszerkezet tulajdonságai:

• út - a csomópontok sorozata,

• hurkot tartalmazó (ciklikus) út - ha az útban 1 csomópont többször is szerepel,

• hurokmentes út -  ha az útban minden csomópont csak egyszer szerepel.