NézetNyomtat

12. óra
Címkék > Óra

12. óra

Gráfalgoritmusokkal kezdünk foglalkozni. Az első témakör a gráfbejárásokat tartalmazza.
A gráfbejárások a legalapvetőbb gráf-algoritmusok. Használhatók keresésre, összefüggő komponensek feltérképezésére, csúcsok gráfban mért távolságának meghatározására, feszítőfák előállítására, és sok más hasznos dologra.
A gráf-algoritmusok vizsgálatát érdemes azzal kezdeni, hogy tisztázzuk, mit is értünk gráf alatt.

Gráf

Sok problémát modellezhetünk úgy, hogy bizonyos "objektumok" közötti kapcsolatokat kell vizsgálnunk, de nem érdekel pontosan az objektumok mibenléte, inkább a kapcsolatok szerkezetére koncentrálunk. Az ilyen problémák kezelésére vezették be a gráf fogalmát:
A $G=(V,E)$ gráf csúcsok egy $V$ halmazával és a csúcsok közötti élek $E$ halmazával adható meg.

1. példa: osztógráf

A gráf csúcsai természetes számok. Az $a$ csúcsból akkor megy él $b$-be, ha $a~|~b$ (és $a\ne b$).
Ebből a példából az is látható, hogy a gráf élei lehetnek irányítottak, ilyenkor számít, hogy egy összekötésnél melyik csúcsból melyik csúcsba mutat az él.

2. példa: metró-térkép

A gráf csúcsai metró-megállók, és két csúcs között akkor megy él, ha egy metrójárat egymás utáni megállói.

Gráfok ábrázolása

A gráfokat különböző módszerekkel tárolhatjuk a memóriában. A három leggyakoribb ábrázolást mutatjuk be az alábbi gráfon:

Él-halmaz

$ \{a\rightarrow b, a\rightarrow c, b\rightarrow d, c\rightarrow d, d\rightarrow a, d\rightarrow b\} $

Szomszédsági listák

a: {b,c}
b: {d}
c: {d}
d: {a,b}

Szomszédsági mátrix

abcd
axx
bx
cx
dxx

Gráfok szélességi bejárása

A szélességi bejárás a gráf egy csúcsából indul, és meglátogatja az összes olyan csúcsot, ami a kiinduló pontból éleken haladva elérhető. A meglátogatás sorrendje a kiinduló csúcstól való távolság szerinti, először a közvetlen szomszédok, utána a másodszomszédok, és így tovább ... kerülnek sorra.
Az ábrán a csúcsokba írt számok azt jelzik, hogy hányadik lépésben ért a bejárás a csúcsba, a színek pedig azt, hogy mely csúcsok vannak azonos távolságra a 0-ás kiinduló csúcstól.

Algoritmus

Szélességi bejárás(G, start)

{előkészületek}
Ciklus minden i csúcsra: 
    szín[i] := fehér
    táv[i]  := végtelen
    apa[i]  := null 
Ciklus vége

{kiinduló csúcs}
szín[start] := szürke
táv[start]  := 0
apa[start]  := null
:= Üres
Sorba(Q,start)

{bejárás}
Ciklus amíg Q nem üres 
    u := Sorból(Q)
    Ciklus u minden v szomszédjára:
        Ha szín[v] = fehér akkor {még nem jártunk itt}
            szín[v] := szürke
            táv[v] := táv[u] + 1
            apa[v] := u
            Sorba(Q,v)
        Elágazás vége
    Ciklus vége
    szín[u] := fekete {ez kész}
Ciklus vége

Eljárás vége

Az algoritmus működése

Az algoritmus megértését segítendő szokás bevezetni a csúcsok színezését, ennek a működés szempontjából nincs igazi jelentőssége, enélkül is megírható a bejárás. A színek a következőt jelentik:
  • fehér: még nem jártunk ebben a csúcsban
  • szürke: már jártunk a csúcsban, de azt még meg kell nézni, innen merre léphetünk tovább
  • fekete: a csúcsot bejártuk, és összes szomszédját is felfedeztük már
A "start" csúcsból indulunk, ő fekete lesz és az összes belőle elérhető csúcsot berakjuk (valamilyen sorrendben) egy sorba. Ezután mindig az történik, hogy amíg van még csúcs a sorban, azt kivesszük (bejárjuk), és összes még nem bejárt szomszédját betesszük a sorba.
A sor adatszerkezet garantálja, hogy így a starttól való távolság sorrendjében látogatjuk meg a gráf csúcsait, hiszen a korábban berakott csúcsokat korábban is vesszük ki a sorból.
A megoldást a táv és apa mezőkben tároljuk. Ezeket a mezőket akkor lehet egy csúcsra kitölteni, amikor bekerül a sorba. A táv azt adja meg, hány élre van a starttól, az apa pedig azt, hogy melyik csúcsból léptünk rá. Az algoritmus futásának végén egy tetszőleges x csúcsból indulva rekonstruálható egy legrövidebb út, az apa "pointerek" végigkövetésével.

A sor adatszerkezet

A bejárás lelke a sor adatszerkezet, itt tartjuk nyilván, hogy melyik csúcsokat kell még bejárnunk, és milyen sorrendben. Bizonyos programozási nyelvekben van előre elkészített sor adattípus, máshol nekünk kell megírni. Megadunk egy lehetséges megvalósítást pascal nyelven.

Feladat