16 - Haladó algoritmusok

Elemi gráf algoritmusok: szélességi, mélységi bejárás és alkalmazásai. Minimális feszítőfák, általános algoritmus, Kruskal és Prim algoritmusai. Legrövidebb utak egy forrásból, sor alapú Bellman-Ford, Dijkstra, DAG legrövidebb út. Legrövidebb utak minden csúcspárra: Floyd-Warshall algoritmus. Gráf tranzitív lezártja.

1. Gráfalgoritmusok

További források

1.1 Gráf ábrázolás

Szomszédossági listás (adjacency list) reprezentáció

A gráf csúcsait helyezzük el egy tömbben (vagy láncolt listában). Minden elemhez rendeljünk hozzá egy láncolt listát, melyben az adott csúcs szomszédjait (az esetleges élsúlyokkal) soroljuk fel.

Szomszédossági mátrixos (adjacency matrix), más néven csúcsmátrixos reprezentáció

Legyen a csúcsok élemszáma \(n\). Ekkor egy \(A^{n×n}\) mátrixban jelöljük, hogy mely csúcsok vannak összekötve. Ekkor mind a sorokban, mind az oszlopokban a csúcsok szerepelnek, és az \(a_{ij}\) cellában a i csúcsból j csúcsba vezető él súlya szerepel, ha nincs él a két csúcs között, akkor \(−∞\) (súlyozatlan esetben 1 és 0)

Amennyiben a gráf irányítatlan nyilván \(a_{ij} = a_{ji}\)

1.2 Szélességi bejárás (BFS: Breadth-first Search)

A szélességi keresés az egyik legegyszerúbb gráfbejáró algoritmus, és ezen alapul sok fontos gráfalgoritmus. Prim minimális feszítÓfákra adott algoritmusa és Dijkstra legrövidebb utat meghatározó algoritmusa a szélességi kereséshez hasonló gondolatmenetet használ.

Adott irányított vagy irányítatlan, összefüggő vagy nem összefüggő gráf és egy kitüntetett \(s\) kezdő csúcs esetén a szélességi keresés módszeresen megvizsgálja a gráf éleit, és így rátalál minden \(s\)-ből elérhető csúcsra. Emellett kiszámitja az összes \(s\)-ből elérhető csúcsba a távolságot, azaz a legkevesebb élt tartalmazó utatat (optimális utatat). Ha több ilyen van, akkor az egyiket. Tehát lehetnek olyan csúcsok és élek, amelyeket nem érint az algoritmus.

Az algoritmus

1. Az s start csúcsot betesszük a sorba
2. A következő lépéseket addig ismételjük, míg a sor üres nem lesz
3. Kivesszük a sor legelsó (u) elemét
4. Azokat a gyerekcsúcsokat, melyeknek a távolsága nem \(∞\) figyelmen kívül hagyjuk (ezeken már jártunk)
5. A többi gyerekre (v): beállítjuk a szülőjét (\(\pi[v] = u\)), és a távolságát (\(d[v] = d[u] + 1\)). Majd berakjuk a sorba.

Műveletigény

• \(n=|G \cdot V|\) (csúcsok száma), \(m=|G \cdot E|\) (élek száma)
• \(M T(n, m) \in \Theta(n+m)\)
• \(m T(n, m) \in \Theta(n)\)

Alkalmazásai

1. Két u és v csomópont közötti legrövidebb út megkeresése, az út hosszát az élek számával mérve (előnye a mélységi kereséshez képest)
2. (Fordított) Cuthill–McKee-háló számozás, a szélességi bejárás egy változata
3. Bináris fa szerializációja/deszerializációja versus szerializáció rendezett sorrendben; lehetővé teszi a fa hatékony újrakonstruálását
4. Egy páros gráf kétoldalúságának tesztelése

1.3 Mélységi bejárás (DFS: Depth First Search)

A mélységi keresés egy gráfbejáró algoritmus. A gráfban a lehető legmélyebben keresünk, azaz a gráf összes élét és csúcsát érintjük. A bemeneti gráf lehet irányított vagy irányítatlan, összefüggő vagy nem összefüggő is. A mélységi keresés gyakran egy másik algoritmus eljárása szokott lenni.

A végeredmény egy mélységi feszítőfa vagy egy mélységi feszítőerdő lesz, attól függően, hogy a gráf összefüggő volt-e. Ahány különböző kezdőcsúcsból indítottunk keresést, annyi mélységi fát hoz létre az algoritmus. Együtt ezek egy mélységi feszítőerdőt fognak alkotni.

Élek felismerése:

• Fa-él \((\Rightarrow)\) fehér csúcsba megyünk
• Vissza-él \((\xrightarrow{V})\) szürke csúcsba megyünk
• Előre-él \((\xrightarrow{E})\) fekete csúcsba megyünk és \(d(u)<d(v)\)
• Kereszt-él \((\xrightarrow{K})\) fekete csúcsba megyünk és \(d(u)>d(v)\)

Az algoritmus

1. Válassz ki egy kezdő csúcsot, és jelöld meg, mint bejárt.
2. Látogasd meg a kezdő csúcs szomszédait egyesével:
   • Ha egy szomszédot még nem látogattál meg:
     • Lépj rekurzívan erre a szomszédra (ismételd a 2. lépést).
3. Ha minden szomszédot meglátogattál, lépj vissza az előző csúcsra.
4. Az algoritmus akkor ér véget, ha minden elérhető csúcsot bejártál.

A mélységi bejárást építőelemként használó algoritmusok

1. Gráf összefüggő komponensének keresése
2. Topológiai rendezés
3. 2- (él vagy csúcs) kapcsolt elemek keresése
4. 3- (él vagy csúcs) kapcsolt elemek megkeresése
5. Separáló élek megkeresése egy gráfban
6. Gráf erősen összefüggő komponenseinek keresése
7. Rejtvények megoldása csak egy megoldással, például labirintusokkal
8. A labirintus létrehozása véletlenszerűen elvégzett mélység-előzetes keresést használhat

1.4 Legrövidebb út kereső algoritmusok (Shortest path algorithms)

Gyakori feladat, hogy egy gráf egy tetszőleges csúcsából bármelyik más csúcsokba vezető legrövidebb utakat keresünk. Gondolhatunk például navigációs rendszerre, ahol a feladat két város közti legrövidebb út meghatározása. Ezt egy gráf segítségével modellezhetjük, a városokat csúcsokkal, a köztük vezető utakat súlyozott élekkel reprezentálhatjuk.

Dijkstra algoritmus

Előfeltétele, hogy a gráfban nem lehet negatív súlyú él, azaz egy \(G: \mathcal{G}_{w}\) gráfra \(\forall(u, v) \in G . E\) élre \(G . w(u, v) \geq 0\). Azért nem lehet benne negatív súlyú él, mert pl. ha egy csúcshoz megtaláljuk a legrövidebb utat, később a negatív élsúly miatt találnánk hozzá rövidebb utat, de az algoritmus minden csúcsot és minden élt legfeljebb egyszer dolgoz fel.

Az algoritmus

1. Az s start csúcs súlyát 0-ra állítjuk eltároljuk
2. A következő lépéseket addig ismételjük, míg a konténerünk üres nem lesz
3. Kivesszük a sor legjobb (u) elemét, és "kész"-re állítjuk
4. Ha egy gyerekcsúcs (v) nem kész, és a jelenleg hozzávezető út súlya kisebb, mint az eddigi, akkor: a szülőjét u-ra állítjuk (\(π[v] = u\)), és a súlyát frissítjük (\(d[v] = d[u] + d(u, v)\)).
5. A többi csúcsot kihagyjuk.

Műveletigény

• \(n=|G . V|\) (csúcsok száma), \(m=|G . E|\) (élek száma)
• \(M T(n, m) \in O((n+m) \cdot \log n)\)
• \(m T(n, m) \in \Theta(n)\)

Bellman-Ford algoritmus

Egy G élsúlyozott (akár negatív) irányított gráf s start csúcsából keres minden élhez minimális költségű utakat, illetve felismeri, ha negatív költségű kör van a gráfban. A d és π tömböket az előzőekhez hasonlóan kezeljük.

Az algoritmus

1. A start csúcs súlyát állítsuk be 0-ra.
2. \(n−1\) iterációban menjünk végig az összes csúcson, és minden csúcsot (u) vessünk össze minden csúccsal (v). Ha olcsóbb utat találtunk akkor v-be felülírjuk a súlyát (\(d[v] = d[u] + d(u, v)\)), és a szülőjét (\(π[v] = u\)).
3. Ha az n-edik iterációban is történt módosítás, negatív kör van a gráfban

Műveletigény

• \(M T(n) \in O(n \cdot m)\)

1.5 Minimális költségű feszítőfa keresése

A minimális költségű feszítőfa vagy minimális feszítőfa egy összefüggő, irányítatlan gráfban található legkisebb élsúlyú feszítőfa. A feszítőfa egy olyan fa, ami a gráf összes csúcsát tartalmazza és élei az eredeti gráf élei közül valók. A minimális feszítőfa nem feltétlenül egyértelmű, de annak súlya igen. Egy gráf tetszőleges minimális feszítőfájának keresésére használható Kruskal és Prim algoritmusa. Mindkét algoritmus mohó stratégiát használ.

Feszítő erdő: A \(G=(V, E)\) irányítatlan gráf feszítő erdeje a \(T=(V, F)\) gráf, ha \(F \subseteq E\) és \(T\) olyan irányítatlan gráf, aminek mindegyik komponense irányítatlan fa, a fák páronként diszjunktak, és együtt éppen lefedik a G csúcshalmazát.

FeszítÓfa: A \(G=(V, E)\) irányitatlan, összefüggő gráf feszitőfája a \(T=(V, F)\) gráf, ha \(F \subseteq E\), és \(T\) fa.

Minimális feszítőfa: A G irányítatlan, összefüggő, élsúlyozott gráf minimális feszítőfája \(T\), ha \(T\) feszitofája \(G\)-nek és bármely másik feszítőfára igaz, hogy az élek összsúlya nagyobb vagy egyenlő, mint \(T\) összsúlya.

Biztonságos él: Biztonságos az él, ha ezzel bővitve egy \(A\) élhalmazt, \(G\) összefüggő, irányítatlan, élsúlyozott gráf valamelyik minimális feszítőfája élhalmazának a részhalmaza marad \(A\). ( \(A \subseteq G\) ).

Általános minimális feszítőfa algoritmus

Kruskal algoritmus

Az éleket súlyuk szerint növekvő sorrendbe rendezzük, és sorra megvizsgáljuk, hogy melyeket vehetjük be a megoldásba. Kezdetben a gráf minden csúcsa egy-egy halmazt alkot. Egy vizsgált él akkor kerül be a megoldásba, ha a két végpontja két különböző halmazban van, mert ebből tudjuk, hogy a vizsgált él hozzáadásával nem keletkezik kör a gráfban. Ekkor a két halmazt egyesítjük. Az algoritmus végére egyetlen halmaz fog maradni.

Az algoritmus

1. Válasszuk ki a legkisebb súlyú élt.
2. Amennyiben az él a részgráfhoz való hozzáadása kört alkot, dobjuk azt el, különben adjuk hozzá.
3. Addig ismételjük a fenti lépéseket, amíg van meg nem vizsgált él.

Alkalmazásai

1. A Kruskal algoritmus annak a tételnek az egyszerű bizonyítására készült, hogy a minimális költségű feszítőfa egyértelmű, ha a gráfban nincs két azonos súlyú él.
2. Véletlen labirintust lehet vele generálni. Ebben az esetben a feldolgozandó gráf minden élének súlya megegyezik, ezért nem kell az éleit rendezni.

Prim algoritmus

A Prim algoritmus egy irányítatlan élsúlyozott (akár negatív) gráf s start csúcsából keres minimális költségű feszítőfát. A d és π tömböket az előzőekhez hasonlóan kezeljük. Az algoritmus egy prioritásos sorba helyezi a csúcsokat.

Az algoritmus

1. A start csúcs súlyát állítsuk be 0-ra.
2. A csúcsokat behelyezzük a prioritásos sorba.
3. A következő lépéseket addig végezzük, míg a prioritásos sor ki nem ürül.
4. Kiveszünk egy csúcsot (u) a sorból.
5. Minden gyerekére (v), amely még a sorban van és a nyilvántartott v-be vezető él súlya nagyobb, mint a most megtalált: A v szülőjét u-ra változtatjuk, a nyilvántartott súlyt felülírjuk \(d[v] = d(u, v)\). Majd felülírjuk a v állapotát a prioritásos sorban.
6. Azokkal a gyerekekkel, melyek nincsenek a sorban, vagy a súlyukon nem tudunk javítani, nem változtatunk.

MÁSKÉPP

Működési elve, hogy csúcsonként haladva építi fel a fát, egy tetszőleges csúcsból kiindulva és minden egyes lépésben a lehető legolcsóbb élt keresi meg egy következő csúcshoz.

Az algoritmus

1. Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
2. Ameddig van az eredeti gráfnak olyan csúcsa, amelyik nincs benne a fában, addig ismételjük az alábbi lépéseket.
3. Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
4. A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.

Alkalmazás: Ezt is lehet véletlen labirintus generálására használni.

1.6 DAG Topologikus rendezése

Alapfogalmak

Topologikus rendezés: Egy G(V, E) gráf topologikus rendezése a csúcsok olyan sorrendje, melyben \(∀(u→v)∈E\) élre u előbb van a sorrendben, mint v

DAG - Directed Acyclic Graph: Irányított körmentes gráf. Legtöbbször munkafolyamatok irányítására illetve függőségek analizálására használják.

Tulajdonságok

• Ha G gráfra a mélységi bejárás visszaélt talál (Azaz kört talált) \(⟹\) G nem DAG
• Ha G nem DAG (van benne kör) \(⟹\) Bármely mélységi bejárás talál visszaélt
• Ha G-nek van topologikus rendezése \(⟹\) G DAG
• Minden DAG topologikusan rendezhető.

DAG topologikus rendezése

Egy G gráf mélységi bejárása során tegyük verembe azokat a csúcsokat, melyekből visszaléptünk. Az algoritmus után a verem tartalmát kiírva megkapjuk a gráf egy topologikus rendezését.

Az algoritmus

1. Indítsunk mélységi bejárást a gráf minden nem látogatott csúcsából
2. Amikor egy csúcsból visszalépünk (minden szomszédját feldolgoztuk), tegyük verembe
3. A mélységi bejárás befejezése után írjuk ki a verem tartalmát
4. Ez ad egy helyes topologikus rendezést
5. Ha visszaélt találunk, a gráf nem DAG

1.7 Legrövidebb utak minden csúcspárra: Floyd-Warshall algoritmus

Célunk egy adott élsúlyozott gráf minden rendezett csúcspárjára a két csúcs közti legrövidebb út megkeresése. Irányított gráf esetén megengedünk negatív éleket, negatív összsúlyú köröket azonban nem, irányítatlan esetben negatív éleket sem engedünk meg.

Az algoritmus leírása

1. Inicializáljuk a \(d[i,j]\) mátrixot: \(\pi(i,j)\) ha van él, \(\infty\) ha nincs, \(d[i,i] = 0\)
2. \(k = 1\)-től \(n\)-ig iterálunk (közbenső csúcsok)
3. Minden \((i,j)\) csúcspárra megvizsgáljuk: jobb út vezet-e \(k\)-n keresztül
4. Ha \(d[i,k] + d[k,j] < d[i,j]\), akkor frissítjük: \(d[i,j] = d[i,k] + d[k,j]\) és \(\pi[i,j] = \pi[k,j]\)
5. Az algoritmus végén \(d[i,j]\) tartalmazza az \(i\)-ből \(j\)-be vezető legrövidebb út hosszát

1.8 Gráf tranzitív lezártja

Első definíció: A \(G = (V, E)\) gráf tranzitív lezártja alatt a \(V × V ⊇ T\) relációt értjük, ahol \((u, v) ∈ T\), ha G-ben az u csúcsból elérhető a v csúcs.

Második definíció: Egy \(G = (V, E)\) irányított gráf tranzitív lezártja az a \(G′ = (V, E′)\) gráf, amelyben u-ból v-be pontosan akkor vezet él, ha u-ból vezet irányított út v-be az eredeti G gráfban.

Minden irányított körmentes gráfhoz (DAG) megfeleltetható a csúcsai egy részbenrendezése, amelyben \(u ≤ v\) pontosan akkor áll fenn, ha a gráfban létezik u-ból v-be menő irányított út. Ugyanakkor egy ilyen részbenrendezést sok különböző irányított körmentes gráf is reprezentálhat. Ezek közül a legkevesebb élt a tranzitív redukált, a legtöbbet a tranzitív lezárt tartalmazza.

Egy gráf tranzitív lezártja könnyen kiszámítható pl. a Floyd-Warshall-algoritmussal \(O(n^3)\) időben, illetve n szélességi kereséssel \(O(n(n+m))\) időben. Ugyanakkor vannak lényegesen hatékonyabb módszerek is, amelyek a gyakorlatban majdnem lineáris időben futnak.

Egy ilyen módszer az erősen összefüggő komponensek meghatározásán, valamint a komponensek gráfjának topologikus rendezésén alapul, de összetett adatszerkezeteket is alkalmaz.

Az algoritmus

1. Inicializáljuk a \(T[i,j]\) mátrixot: \(\text{true}\) ha van él vagy \(i = j\), \(\text{false}\) egyébként
2. \(k = 1\)-től \(n\)-ig iterálunk (közbenső csúcsok engedélyezése)
3. Minden \((i,j)\) csúcspárra megvizsgáljuk: létezik-e út \(k\)-n keresztül
4. Ha \(T[i,k] \land T[k,j] = \text{true}\), akkor \(T[i,j] = \text{true}\)
5. Az algoritmus végén \(T[i,j]\) megmondja, hogy elérhető-e \(j\) az \(i\)-ből

Summary