Gráfalgoritmusok
Feszítőfa
Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf. Feszítőfából általában több is van.
Minimális feszítőfa
A minimális feszítőfa egy gráfban a legkisebb élsúlyú feszítőfa.
Kruskal-algoritmus
A Kruskal algoritmus segítségével minimális feszítőfát lehet megtalálni.
Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt. Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.
Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör. Ha mégis kör keletkezne, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.
Ezt addig csináljuk, amíg kész nem vagyunk.
Gráfok szélességi keresése (BFS)
Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).
Működése:
Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot. Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.
Most ezeknek keressük meg az 1 egység távoli szomszédjait. De csak azokat, akiken még nincsen címke.
Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.
Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg. Mindegy melyiket.
Az algoritmus aztán így folytatódik, és szép lassan végez.
Gráfok mélységi keresése (DFS)
A DFS (Depth-first search) algoritmus a gráf mélységi bejárása.
A DFS algoritmus lényege, hogy elindulunk egy úton, és megyünk, amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk, akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
Amikor újra elakadunk, megint visszamegyünk, és ezt ismételjük, amíg az egész gráfot be nem jártuk.
BFS fa és DFS fa
A BFS és DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket nevezzük BFS és DFS fának.
Adjuk meg ennek a gráfnak a minimális súlyú feszítőfáját a Kruskal-algoritmus segítségével.
Térképezzük föl az alábbi gráfot a szélességi bejárás (BFS) segítségével.
Térképezzük föl az alábbi gráfot a mélységi bejárás (DFS) segítségével.
a) Íme, egy gráf két különböző kezdőpontjából készített BFS fája:
Adjuk meg az eredeti gráfot.
b) Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája:
Adjuk meg az eredeti gráfot.
Térképezzük föl az alábbi gráfot a Dijkstra algoritmus segítségével.
Ez a vasúti hálózat egy gráf.
Megmutatja, hogy mely állomások között vezetnek vasútvonalak.
Ha ellátjuk az éleket súlyokkal…
Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.
Vagy hány percig tart a két állomás közötti út.
Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.
Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…
akkor a gráfnak egy feszítőfáját kapjuk.
Feszítőfából általában több is van.
És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…
Van itt ez a gráf, és rendeljünk hozzá az éleihez nem negatív valós számokat.
Ezeket a számokat súlyoknak nevezzük.
Képzeljük el, hogy ez a gráf egy úthálózat, vagy mondjuk egy elektromos hálózat, az élek súlyai pedig az áthaladás költsége.
Készítsük el ebben a gráfban a minimális súlyú feszítőfát.
Ez egy olyan hálózat lesz, amin keresztül bármely csúcsból bármely csúcsba el lehet jutni, de a benne szereplő élek súlyainak összege minimális.
Vagyis ez a legolcsóbban működtethető olyan hálózat, ami az összes csúcsot tartalmazza.
A minimális feszítőfát a Kruskal algoritmus segítségével lehet megtalálni.
Maga az algoritmus nagyon egyszerű.
Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt.
Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.
Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör.
Ha mégis kör keletkezik, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.
Most éppen van még egy 1-es él…
sőt még egy.
Aztán jönnek a 2-es élek.
Hopp, itt keletkezett egy kör.
Az nem jó, akkor ezt a legutóbbi élt töröljük.
A 2-esekbből kifogytunk, jönnek a 3-asok.
Elfogytak a 3-asok is, úgyhogy jöhetnek a 4-esek.
Ajaj, úgy tűnik mégse…
Hát akkor jöhet az 5-ös.
Aztán a 6-os.
Abból úgy tűnik csak ez az egy van.
Aztán itt jönnek a 7-esek.
A 8-asok…
Végül a 9-esek.
És voila, itt a minimális súlyú feszítőfa.
Az algoritmus röviden így írható le:
Legkisebb súlyú él kiválasztása
Kör keletkezik:
az élt töröljük
Nem keletkezik kör:
az élt megtartjuk
Vesszük a megmaradó
ki nem választott éleket
Egy gráfban lehet több minimális feszítőfa is.
Ez most is így van..
Van itt ez a gráf.
És szeretnénk föltérképezni egy adott pontjából kiindulva.
Az egyik módszer a gráf földerítésére a szélességi keresés.
A BFS algoritmus működése nagyon egyszerű.
Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot.
Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.
Most ezeknek keressük meg az 1 egység távoli szomszédjait.
De csak azokat, akiken még nincsen címke.
Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.
Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg.
Mindegy melyiket.
Itt jönnek aztán a kiindulóponttól 3 egység távolságra lévő pontok.
És persze itt is elég egy él.
Az algoritmus folytatódik. Most a 3-as címkéjű pontoknak keressük meg a szomszédjait.
És szép lassan végzünk.
A BFS algoritmus úgy működik, mint egy hullám, ami a gráf élein szétterjed.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre átfésülik a gráfot.
Nyomozni persze nem csak a különleges alakulatok tudnak…
hanem a magányos detektívek is.
Akik idejüket nem kímélve egyedül bejárják a gráf minden zegzugát.
Ez egy egészen más mentalitást igényel, amit mélységi keresésnek nevezünk.
A gráfok bejárásának egyik lehetséges módját már láttuk.
Ez a BFS algoritmus, ami hullámszerűen fésüli át a gráfot.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre teljes szélességben haladnak.
De nyomozni nem csak a különleges alakulatok tudnak, hanem a magányos detektívek is.
Ezt DFS algoritmusnak nevezzük.
A DFS algoritmus a gráf mélységi keresés.
A DFS algoritmus lényege, hogy elindulunk egy úton…
rendíthetetlenül.
És megyünk amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk…
Akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
És megyünk a járatlan utakon tovább.
Amikor újra elakadunk, megint visszamegyünk.
Hopp.
Hát, ez ennyi.
Végül itt még vannak lehetőségek.
Így működik a mélységi bejárás.
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk.
Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük.
Mindketten az eredeti gráf feszítőfái.
Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek.
Ha például itt egy másik élt húzunk be…
akkor egy egészen más BFS fát kapunk.
Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk.
Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján.
Íme, egy gráf két különböző kezdőpont alapján készített BFS fája:
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük. Mindketten az eredeti gráf feszítőfái. Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek. Ha például itt egy másik élt húzunk be… akkor egy egészen más BFS fát kapunk. Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk. Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján. Íme, egy gráf két különböző kezdőpont alapján készített BFS fája: Adjuk meg az eredeti gráfot. Lássuk, hogyan tudnánk hasznosítani a BFS fákat. Készítünk egy ilyen kis szomszédsági táblázatot. Aztán pedig kezdjük is az első BFS fával. Eddig jó. Vannak még kétségek, de ezeket reméljük a másik BFS fa hamarosan eloszlatja. Az, hogy a C és D csúcsok között vezet él, immár biztosabb, mint a halál. Hát, ez kész. Már csak föl kell rajzolnunk. Csodás. Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája: Hát, úgy tűnik eddig jutottunk. Nem baj, azért kezdjünk el rajzolgatni. Ezek itt a kérdőjeles élek. Viszont tudjuk még, hogy a gráf minden csúcsának a fokszáma páros. Ha mindkét élt elhagyjuk, az nem jó, mert akkor lesz páratlan fokszámú csúcs. És, ha mindkét élt behúzzuk, az se jó, mert akkor keletkezik harmadfokú csúcs. Ha csak az egyik élt húzzuk be… akkor így lesz egy elsőfokú csúcs. Így viszont minden csúcs páros fokszámú.
