Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6.2. A mélységi keresés

6.2. A mélységi keresés

  1. éleit vizsgálja, mindig az utoljára elért, új kivezető élekkel rendelkező csúcsból kivezető, még nem vizsgált éleket deríti fel. Az összes ilyen él megvizsgálása után visszalép és azon csúcs éleit vizsgálja, amelyből -t elértük.

  2. Az összes csúcsot megvizsgálja.

  3. Létrehoz egy ,,mélységi erdőt”, amely az előd részgráf fáiból áll.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, szürke lesz, mikor elértük, és fekete, mikor elhagytuk.

  5. Minden csúcshoz két időpontot rendel, az elérési és az elhagyási időpontot .

6.9. Definíció. A gráfot előd részgráfnak nevezzük, ha

6.10. Tétel. [Zárójelezés tétele]

Mélységi keresést alkalmazva egy (irányított, vagy iráyítatlan) gráfra a következő 3 feltétel közül pontosan 1 teljesül bármely és csúcsra:

a és a intervallumok diszjunktak,

a intervallum tartalmazza a intervallumot, és az csúcs a csúcs leszármazottja a mélységi fában,

a intervallum tartalmazza a intervallumot, és a csúcs az csúcs leszármazottja a mélységi fában.

6.11. Következmény. [Leszármazottak intervallumainak beágyazása]

A csúcs akkor és csak akkor leszármazottja az csúcsnak az irányított, vagy irányítatlan gráf mélységi erdejében, ha .

6.12. Tétel. [Fehér út tétele]

Egy gráfhoz tartozó mélységi erdőben a csúcs akkor és csak akkor leszármazottja az csúcsnak, ha elérésekor a időpontban a csúcs elérhető -ból olyan úton, amely csak fehér csúcsokat tartalmaz.

A mélységi keresés révén a mélységi kereséstől függően a bemeneti gráf éleit osztályozhatjuk. Éltípusok: egy él

  1. Fa él, ha a mélységi erdő éle.

  2. Visszamutató él, ha megelőzője -nak egy mélységi fában.

  3. Előre mutató él, ha leszármazottja -nak egy mélységi fában.

  4. Kereszt él, ha a fenti három osztályba nem sorolható be

Irányított gráf akkor és csak akkor körmentes, ha a mélységi keresés során nem találtunk visszamutató éleket.

6.13. Tétel. Egy irányítatlan gráf mélységi keresésekor bármely él vagy fa él, vagy visszamutató él.

Egy irányított gráf topologikus rendezése a csúcsainak sorba rendezése úgy, hogy ha -ben szerepel az él, akkor előzze meg -t a sorban

6.14. Tétel. A TOPOLOGIKUS_RENDEZÉS() egy írányított, körmentes gráf topologikus rendezését állítja elő.