Gráfbejáró algoritmusok

A gráfok alkalmazásairól sok szó esett az Algoritmusok és gráfok tárgyon. Jelölhetik a gráfok csúcsai a városokat, az éleik a közöttük futó utakat. Vagy jelölhetnek a csúcsok felhasználókat, az élek pedig azt, hogy ki kit ismer, mint egy közösségi portálon. Esetleg a csúcsok jelölhetnek függvényeket, az élek pedig azt, hogy melyik függvény melyik másik függvényeket hívja meg; egy ilyen gráf sokat segíthet abban, hogy egy nagy programot áttekintsünk. Vagy a csúcsok egy játékban, pl. sakkban egy játékállást reprezentálnak, az abból kiinduló élek pedig olyan csúcsokba vezetnek, amelyek egy játéklépéssel elérhetőek.

Most a konkrét alkalmazásokkal nem fogunk foglakozni, csak azzal, hogy a gráfos algoritmusokat, a tárolást és a bejárásokat hogyan valósíthatjuk meg Pythonban. Az ábrázolások (tárolási módszerek) közül is most először csak az éllistás tárolással foglalkozunk (adjacency list), méghozzá egyszerű, irányított gráfokra.

Az éllistás ábrázolásban a csúcsokat megszámozzuk, és betesszük őket egy tömbbe. A tömb minden eleme tehát egy csúcs, és a tömbelemek indexeivel hivatkozni tudunk rájuk. Az egyes csúcsokhoz tartozóan az azokból kiinduló éleket pedig listába tesszük. A fenti gráfon az A jelű csúcsból indul él a B és a C jelű csúcsba; ezért az A csúcs adatait tartozó 0. tömbelem éllistájában szerepel az 1-es és 2-es szám, vagyis onnan indul él az 1-es indexű (B) és a 2-es indexű (C) csúcshoz. C-ből nem megy él sehova, ezért a C csúcs éllistája üres.

Éllistás reprezentáció

Éllistás reprezentáció,
Python sajátosságokhoz igazítva

Miért különböztetjük meg a csúcsok tömbjét és az élek listáját? Mi a jelentősége annak, hogy az egyiknél tömböt, a másiknál listát mondunk? Ha a gráf módosítására gondolunk, akkor hamar megjelenik a különbség. Új élt könnyű behúzni és törölni, a módosítás nincsen hatással a gráf reprezentációjának, vagyis az adatszerkezetnek a többi részére.

Ha azonban a csúcsokat szeretnénk módosítani, főleg ha egy csúcsot szeretnénk törölni, akkor már nem ilyen egyszerű a feladat. Tegyük fel, hogy a B csúcsot szeretnénk törölni a gráfból, értelemszerűen a belőle kiinduló és az őt célba vevő élekkel együtt. Ehhez nem elég csak simán törölni az 1-es indexű tömbelemet. Ezen felül két további dolgunk is van még:

• Végig kell néznünk az összes éllistát, hogy van-e valahol hivatkozás az 1-es csúcsra (az volt a B). Ha igen, akkor azt is törölni kell.
• Bár a gráfban a csúcsoknak nincs sorrendje (halmaznak tekintjük őket), ebben az ábrázolásban van, mert az éllisták indexek szerint hivatkozzák a csúcsokat. Amiatt is végig kell néznünk a listákat, hogy a B utáni csúcsok indexei megváltoztak. A C csúcs 1-es indexűvé, a D csúcs 2-es indexűvé változik a törlés által, vagyis az összes B utáni csúcs indexei eggyel csökkennek. Ezt a módosítást is végig kell vezetnünk mindenhol.

Emiatt a csúcsok tárolóját fix méretűnek, tömbnek szoktuk tekinteni, az élek listáját pedig változtathatónak, láncolt listának. A csúcsok tömbjében számít a sorrend is (mert az élek sorszám szerint hivatkoznak rájuk), az élek listájában viszont lényegtelen. Nem megoldhatatlan, de hosszadalmas feladat a csúcsok átszámozása.

Tömböt Pythonban a list típussal szoktunk létrehozni, mert ez lehetővé teszi az objektumaink hatékony elérését és indexelését. Érdemes ugyanezt a típust használni az élek listájához is, mert tudjuk, hogy néhány speciális esettől eltekintve (elejére beszúrás, elejéről törlés) ez a leghatékonyabb tároló. Vagyis mindkettőhöz a Python listát használjuk majd.

A gráf tárolására három osztályt definiálunk: a gráfot, a csúcsot és az élt.

class Graf:
    def __init__(self, nev=None):
        self.nev = nev
        self.csucsok = []

class Csucs:
    def __init__(self, nev=None):
        self.nev = nev
        self.elek = []

class El:
    def __init__(self, cel, suly=None):
        self.suly = suly
        self.cel = cel

g = Graf("Térkép")
g.csucsok.extend([Csucs("A"), Csucs("B"), Csucs("C")])
g.csucsok[0].elek.extend([El(1, 10), El(2, 15)])

A Graf osztályunk egy gráf adatait tartalmazza. Az algoritmusok szempontjából leglényegesebb persze a csúcsokat tároló list lesz, de a gráf további adatokat is tartalmazhat, pl. a gráf nevét, vagy amit szeretnénk.

Ugyanez a helyzet a Csucs osztállyal. Az éllista mellett bármilyen adatokat tartalmazhat, jelen esetben ez is egy nevet. Alul látszik is, hogy konstruktorban megadhattuk a csúcsok neveit, így a programban is ugyanaz az A, B és C címke jelöli meg a csúcsokat, mint a rajzon.

Harmadik osztályunk az El. Ennek kötelező adattagja a cél (hova, hányas indexű csúcsba fut az él a gráfban), és az előzőekhez hasonlóan adatokat is tartalmazhat, például az él súlyát.

A gráf felépítése a két lista kitöltéséből áll. (A listák .extend() függvénye olyasmi, mint az .append(), de nem egy, hanem több elemet is hozzá tud adni egyszerre.) Egy dologra kell csak figyelni, az élek indexeire. A példában az A, B, C csúcsokat adtuk hozzá a gráfhoz, tulajdonképp itt kapták meg azok a 0, 1, és 2 indexeket.

g.csucsok[0].nev             # A
g.csucsok[0].elek[1].suly    # A → C, 15

Ezekkel az osztályokkal és adattagokkal elértük azt, hogy a gráf adatait szemléletesen, könnyen érthető kifejezésekkel elérjük. Pl. a g.csucsok[0].nev az első csúcs nevét adja, jelen esetben A-t. A g.csucsok[0].elek[1].suly az egyik él súlyát adja meg, amelyik ebből a csúcsból indul ki – az A → C élről van szó.

A legfontosabb gráfos algoritmusok a gráfbejárások.

A mélységi bejárásban (depth-first search, DFS) mohón haladunk előre az élek mentén addig, ameddig csak lehet, és csak utána fordulunk vissza. Vagyis nem egy csomópont összes élét, összes szomszédját vizsgáljuk előbb, hanem ahogy meglátunk egy szomszédot, egyből megyünk is arra tovább, amíg csak lehet.

A mohó haladás az élek mentén nagyon egyszerűen megvalósítható rekurzióval. Ahogy találunk egy élt v csúcsból w-be, rögtön rekurzívan meghívjuk a bejárást arra a csúcsra, amelyikbe az vezet – így a v csúcsból induló további élek csak akkor fognak sorra kerülni, ha ez a rekurzív hívás már visszatért.

mélységi_bejárás(v):
    v-t bejártnak jelölni
    MINDEN v → w élre:
        HA w nincs bejárva:
            mélységi_bejárás(w)    rekurzió
            <tevékenység v → w élre>
    <tevékenység v csúcsra>

bejárva = ∅
mélységi_bejárás(s)     indítás s-ből

A bejárás közben valamilyen tevékenységet elvégezhetünk a csúcsokra és az élekre is. Pl. kiírhatjuk a csúcsokban tárolt adatot, feljegyezhetjük, milyen úton jutottunk el egy csúcshoz és így tovább. Ezekkel most nem foglalkozunk, csak a pszeudokódban jelöltük a helyüket.

Az algoritmus nagyon hasonlít a bináris fákat bejáró rekurzív függvényekhez. A különbség a bejárt élek kezelésében rejlik. A gráf, amelyet bejárunk, nem biztos, hogy fa. Tehát előfordulhat, hogy egy csúcsba több úton is eljutunk. Erre figyelni kell, mert a bejárásban nem akarunk egy csúcsot többször feldolgozni. Például az alábbi gráfban a 0-s csomópontból két úton is eljuthatunk a 4-es csomóponthoz: a 0→4 éllel közvetlenül, továbbá a 0→1→4 úton is.

A meglátogatott csúcsok megjelölésére azért is szükség van, mert kör lehet a gráfban. Ha erre nem figyelnénk, akkor az élek mentén körbe-körbe mennénk a gráfban, soha nem állna meg az algoritmus. Ez történne a 0→2→5→0 körön. Emiatt tudnunk kell valamilyen módon, hogy melyik csúcsnál jártunk már, és melyiknél nem. A pszeudokód vonatkozó sorai:

v-t bejártnak jelölni
HA w nincs bejárva

Vajon milyen adatszerkezetet használhatnánk ennek a tárolására? Lehetőségeink:

• Tömb: bejárva = [False] * len(csúcsok)
• Halmaz: bejárva = set()
• Szótár: bejárva = dict()
• A csúcsnál: graf.csucsok[v].bejarva

Megoldhatjuk a problémát egy tömbbel (Pythonban: listával). A tömböt kezdetben csupa Hamis értékekkel inicializáljuk, és amikor bejártnak jelölünk egy csúcsot, akkor a hozzá tartozó indexre Igaz értéket kell tenni. Ha a teljes gráfot be szeretnénk járni, akkor praktikusabb a tömbös megoldást választani, mert hatékonyabb lesz. Előre tudjuk, ennek a tömbnek hány eleme van: annyi, amennyi csúcsa a gráfnak.

A halmaz típus is adja magát erre a feladatra. Jártunk-e egy adott helyen: bent van-e a csúcs indexe a halmazban. Végül pedig, eszünkbe juthat a szótár típus. Ebben is ellenőrizni tudjuk, egy adott kulcs szerepel-e a szótárban vagy nem. De itt a kulcsokhoz értékeket is tárolhatunk; valamilyen adatot feljegyezhetünk bejárás közben minden csúcshoz. Pl. honnan érkeztünk oda; hány lépés kellett, hogy eljussunk oda, és így tovább.

Megoldás lehet az is, ha ezt az információt egyszerűen a csúcsnál tároljuk, vagyis a Csucs osztályban létrehozunk erre egy adattagot. Ez nem a legszebb megoldás, de egyszerűsége miatt néha szokták ezt a módszert alkalmazni.

A bejárt elemek nyilvántartásához most halmazt használunk. A bejáró függvényünk, a melysegi_bejaras_seged() rekurzív. Ez fontos a bejárt elemeket tároló halmaz szempontjából: akármilyen távolra megyünk az eredeti csúcstól, tehát akármelyik rekurzív hívásról van szó, a bejárt csúcsok indexeit tároló halmaz objektumból csak egy példány kell legyen.

Ezt megoldhatnánk úgy is, hogy mindig paraméterként adjunk neki a halmazt, amivel dolgoznia kell, de van ennél jobb megoldás is, mégpedig a következő. A „külső” függvényben, a melysegi_bejaras()-ban létrehozzuk a halmazt. Továbbá definiálunk azon belül egy újabb függvényt, amelyik a bejárást végző rekurzív függvény lesz. Ez látja a külső függvény által definiált változót, és a külső függvény paramétereként látszó gráfot is. Paramétere így csak egyetlen egy kell legyen, a csúcs sorszáma, ez pedig a v nevű.

def melysegi_bejaras(graf, start):
    def melysegi_bejaras_seged(v):
        bejarva.add(v)
        print(graf.csucsok[v].nev) # v csúcs
        for el in graf.csucsok[v].elek:
            w = el.cel
            if w not in bejarva:
                melysegi_bejaras_seged(w) # v→w él

    bejarva = set()
    melysegi_bejaras_seged(start)  # vagy az összesből

Egyébiránt az algoritmus egy az egyben a pszeudokódot valósítja meg, igazítva a gráf felépítéséhez használt típusainkhoz: a Graf, Csucs és El osztályokhoz.

def melysegi_bejaras(graf):
    def melysegi_bejaras_seged(v):
        # ...

    bejarva = set()
    for start in len(graf.csucsok):
        if start not in bejarva:
            melysegi_bejaras_seged(start)

A szélességi bejárásban (breadth-first search, BFS) a csúcsokat olyan sorrendben dolgozzuk fel, hogy előbb a kiindulási helyhez közelebbi csúcsok kerülnek sorra. Vagyis meglátogatjuk (visit) az első csúcsot, majd annak a szomszédait, majd ezen szomszédok olyan szomszédjait, ahol még nem voltunk, és így tovább.

A szélességi bejáráshoz egy várakozási sort használunk, amelyet az alábbi pszeudokód Q-val jelöl. Ennek mindig a végére rakjuk azokat a csúcsokat, ahova épp élt látunk indulni, hogy később majd velük is foglalkozzunk. A sor végére így a kiindulási helytől távolabbi csúcsok kerülnek, a sor elején pedig azok a csúcsok várakoznak, amelyeket legrégebb óta a sorban vannak – vagyis akik közelebb voltak a kiindulási helyhez.

s-t bejártnak jelölni
Q = [s]
AMÍG Q ≠ ∅:
    v = Q elejéről kivenni
    MINDEN v → w élre:
        HA w nincs bejárva:
            w-t bejártnak jelölni
            Q végére w-t betenni
            <tevékenység v → w élre>
    <tevékenység v csúcsra>

Az algoritmus a meglátogatott csúcsok kezelése miatt működne köröket tartalmazó gráfra is. Az ábra egy fára mutatja be, milyen sorrendben kerülnek feldolgozásra az elemek.

Az algoritmushoz tehát szükségünk van egy várakozási sorra:

Q = [s]
AMÍG Q ≠ ∅:
v = Q elejéről kivenni
Q végére w-t betenni

Előbb láttuk, hogy ilyen van beépítve: a collections modul queue osztálya épp ezt tudja. Az alábbi függvény szélességi bejárást végez a graf referenciával adott gráfon a start indexű élből kiindulva.

def szelessegi_bejaras(graf, start):
    bejarva = set([start])
    sor = deque([start])    # várakozási sor
    while sor:
        v = sor.popleft()
        for el in graf.csucsok[v].elek:
            w = el.cel
            if w not in bejarva:
                bejarva.add(w)
                sor.append(w)
        print(graf.csucsok[v].nev)

Mélységi bejárás iteratívan?

Egy kis apróbetűs kitérő.

A mélységi bejárás iteratívan is lehetséges. Az algoritmus alapötlete és felépítése szinte teljesen megegyezik a szélességi bejáráséval. A lényegi különbség az, hogy itt sor helyett vermet használunk.

def melysegi_bejaras_iterativ(graf, start):
    bejarva = set()
    verem = deque([start])    # verem
    while verem:
        v = verem.pop()
        if v not in bejarva:
            bejarva.add(v)
            for el in graf.csucsok[v].elek:
                verem.append(el.cel)
            print(graf.csucsok[v].nev)

Hasonlítsuk össze a két algoritmus működését! A szélességi keresésben mindig azokkal a csúcsokkal foglalkozunk, amiket legrégebben beraktunk a várakozási sorba. Ezek azok lesznek, amelyek közelebb vannak a kiinduló élhez, mert a sorba beszúrt új elemek mindig távolabb vannak tőle (azokhoz egy él feldolgozásával jutottunk). Ezzel szemben a mélységi keresésben mindig olyan csúcsra lépünk, amelyekhez a legutóbb feldolgozott csúcsból jutottunk. Így megyünk a keresésben nagyon hamar távolra a kiindulási csúcsból.

Tehát a szélességi keresésben a legrégebbi csúccsal foglalkozunk mindig, a mélységi keresésben pedig a legutóbb felfedezettel. A szélességi és a mélységi keresés között a lényegi különbséget a tároló adja: a szélességi keresés várakozási sort, a mélységi keresés vermet használ. A konkrét alkalmazásokban, az adott feladathoz igazított verziónál ennél persze nagyobb különbség is lehet, de a lényeg ez.

Adott az alábbi gráfunk, amelyet szélességi bejárással szeretnénk feldolgozni a 0-val jelzett csúcsból indulva.

Tudjuk, hogy a szélességi bejárás egy adott csúcsból kiindulva a legrövidebb utak megtalálására kiválóan alkalmas. Ez abból adódik, hogy előbb a kiindulási csúcs szomszédaira lép, és csak ha mind bejárta a kiinduló csúcs közvetlen szomszédait, akkor megy majd tovább azok szomszédjaira – vagyis az olyan csúcsokra, amelyek már két ugrásnyi távolságra vannak a kiinduló csúcsból. Ezek alapján szinteket különböztethetünk meg a bejárásban. A 0. szint a kiindulási hely. Az 1. szinten vannak azok a csúcsok, amelyek onnan közvetlenül elérhetőek. A 2. szinten azok, amelyekhez az 1. szint csúcsaiból vezet él, és így tovább. Az ábrán szándékosan úgy lettek elhelyezve az élek, hogy ez jól látszódjon: ha mondjuk lenne egy 0→6 él, akkor a 6-ossal jelzett csúcs is az 1. szintre kerülne.

A várakozási sorba tehát az alábbihoz hasonló rendben kerülnek be az elemek:

←  0 ... (1 4 2) ... (3 5 6) ... (8 7)  ←

A zárójeles csoportokon belül a sorrend nem definiált, de az biztos, hogy előbb a 0 jön (onnan indultunk), utána pedig az első szint elemei, aztán pedig a második szint elemei. Sőt a sorban mindig csak olyan csúcsok vannak, amik legfeljebb egy szintnyi távolságban vannak egymástól! Miért? Mert amíg nem végeztünk egy adott szint összes csúcsaival, addig nem fogunk foglalkozni a következő szint csúcsaival, amelyekből a kettővel lentebbi csúcsok elérhetőek lennének.

Lássuk ezt a konkrét példán! A sorba betesszük a 0-t, így indul a feldolgozás. Ezek után a sorba az 1, 4, 2 csúcsok kerülnek, a 0 pedig eltűnik onnan. A következő „körben” az 1, 4, 2 csúcsok szomszédai fognak bekerülni a sorba, vagyis a 3, 5 és a 6. De amíg nem végeztünk az 1. szint elemeivel, addig teljesen biztosan a 7 nem fog a várakozási sorba kerülni; ahhoz előbb a 3-nak és az 5-nek sorra kellene kerülnie.

Vezessünk be egy új elnevezést. Nevezzük a szélességi bejárás frontjának annak a szintnek a csúcsait, amelyeket a bejáró algoritmus épp feldolgoz. Kezdetben a 0. szint csúcsától indul. Aztán az 1. szint csúcsait fogja vizsgálni; ekkor a bejárás frontja az 1. szinten van, és ilyenkor ismerjük meg a 2. szint csúcsait. Utána a bejárás frontja továbbhalad a 2. szintre, és az onnan induló élek mutatják meg a 3. szintet.

Ha a bejárás frontjának csúcsait, és a következő szint csúcsait külön tárolóba tesszük, akkor a várakozási sortól meg tudunk szabadulni. Lássuk, hogyan!

def szelessegi_bejaras(graf, start):
    bejarva = [False] * len(graf.csucsok)
    front = [start]   # lista!
    while front:
        print(front)  # debug
        kovetkezo = []
        for v in front:
            for el in graf.csucsok[v].elek:
                w = el.cel
                if not bejarva[w]:
                    bejarva[w] = True
                    kovetkezo.append(w)   # csak append
            print(graf.csucsok[v].nev)
        front = kovetkezo

[0]
[1, 4, 2]
[3, 5, 6]
[8, 7]