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
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)
Ciklus minden i csúcsra:
szín[i] := fehér
táv[i] := végtelen
apa[i] := null
Ciklus vége
szín[start] := szürke
táv[start] := 0
apa[start] := null
Q := Üres
Sorba(Q,start)
Ciklus amíg Q nem üres
u := Sorból(Q)
Ciklus u minden v szomszédjára:
Ha szín[v] = fehér akkor
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
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
