Irányított gráfok, gráfalgoritmusok irányított gráfokban
DFS-algoritmus irányított gráfokban
A DFS algoritmusnak az a lényege, hogy kiindulunk egy csúcsból, és megyünk ameddig tudunk.
Az, hogy merre megyünk, teljesen a véletlen műve.
Egyszer aztán elérkezünk egy olyan pontba, ahonnan már nincs tovább.
Innen már csak olyan csúcsba tudnánk továbblépni, ahol korábban már jártunk.
Ekkor visszaugrunk egészen addig, ahonnan még vezet út bejáratlan csúcsba.
Ha már minden csúcshoz eljutottunk, akkor a DFS algoritmus véget ér.
DFS-fa
A DFS algoritmus eredményeként kapjuk a DFS-fát.
Hogyha a DFS-fába berajzoljuk az eredeti gráf többi élét is, akkor ezek az élek három típusba sorolhatóak. Vannak olyan élek, amelyek képesek lerövidíteni egy utat a DFS fában. Ezeket az éleket úgy hívjuk, hogy "előre-él". Ha az eredeti gráfban van fordított irányú él, akkor ezt az élt "vissza-él"-nek nevezzük. Hogyha az eredeti gráfban van $u$-ból $v$-be vezető él, akkor ezt az élt "kereszt-él"-nek nevezzük.
BFS-algoritmus irányított gráfokban
A BFS-algoritmus lényege, hogy kiindulunk egy csúcsból, aztán megkeressük a közvetlen szomszédjait. Innen folytatódik az algoritmus, és az új csúcsoknak keressük meg a szomszédjait. Ha több él is vezet egy szomszéd felé, mindegy melyiket választjuk. Az algoritmust addig ismételjük, amíg minden csúcsot meg nem találtunk.
BFS-fa
A BFS algoritmus eredményeként kapjuk a BFS-fát.
Hogyha a BFS-fába berajzoljuk az eredeti gráf többi élét is, akkor ezek az élek három típusba sorolhatóak.
Vannak "előre-él"ek, "vissza-él"ek és "kereszt-él"ek.
Dijkstra algoritmus
A Dijkstra algoritmus képes megtalálni a gráf egy adott csúcsából a többi csúcsba vezető legrövidebb utat.
Az algoritmus lényege, hogy kiválasztunk egy pontot, és ebből a pontból kiindulva csúcsról csúcsra haladva felderítjük az egész gráfot.
Derítsük föl az alábbi gráfot az 1-es csúcsból indulva a Dijsktra algoritmus segítségével.
Írjuk fel az alábbi gráf bármely két csúcsa közti távolságokat a Floyd algoritmus segítségével.
Most őrülten izgalmas dolgokat fogunk csinálni irányított gráfokkal. Megnézzük, hogy az irányított gráfokban hogyan működnek a különböző gráf-algoritmusok. Kezdjük a DFS algoritmussal, vagyis a gráfok mélységi keresésével. A mélységi keresés valójában nagyon egyszerű. A DFS algoritmusnak az a lényege, hogy kiindulunk egy csúcsból… és megyünk ameddig tudunk. Az, hogy merre megyünk, teljesen a véletlen műve. Egyszer aztán elérkezünk egy olyan pontba, ahonnan már nincs tovább. Innen már csak olyan csúcsba tudnánk továbblépni, ahol korábban már jártunk. Ekkor visszaugrunk egészen addig… ahonnan még vezet út bejáratlan csúcsba. Ha már minden csúcshoz eljutottunk, akkor a DFS algoritmus véget ér. A DFS algoritmus eredményeként kapjuk a DFS-fát. Hogyha a DFS-fába berajzoljuk az eredeti gráf többi élét is, akkor ezek az élek három típusba sorolhatóak. Vannak olyan élek, amelyek képesek lerövidíteni egy utat a DFS fában. Ezeket az éleket úgy hívjuk, hogy „előre-él”. Legyen u és v két olyan csúcs, amelyek a DFS-fában nem szomszédosak és vezet út u-ból v-be. Hogyha az eredeti gráfban van u-ból v-be vezető él, akkor ezt az élt „előre-él”nek nevezzük. ELŐRE-ÉL Itt van aztán ez a másik él is. Ez pont olyan, mint az „előre-él” csak éppen visszafelé mutat. Legyen u és v két olyan csúcs a DFS-fában, hogy vezet út u-ból v-be. Hogyha az eredeti gráfban van fordított irányú, vagyis v-ből u-ba vezető él, akkor ezt az élt „vissza-él”nek nevezzük. Itt most van még néhány „vissza-él”. Vannak aztán olyan élek is, amelyek a DFS-fa két különböző ágát kötik össze. Legyen u és v két olyan csúcs a DFS-fában, hogy sem u-ból v-be, sem v-ből u-ba nem vezet út. Hogyha az eredeti gráfban van u-ból v-be vezető él, akkor ezt az élt „kereszt-él”nek nevezzük. A DFS-fa rengeteg hasznos információt árul el az eredeti gráf szerkezetéről. Ha a DFS-fában van vissza-él, az azt jelenti, hogy a gráf ciklikus. Tehát körbe lehet menni. Éppenséggel most elég sokféleképpen… Hogyha az eredeti gráf aciklikus, vagyis nincsenek benne körök… az DFS-fa alapján is azonnal kiderül: Nincsenek benne vissza-élek. Most, hogy mindezt megtudtuk, lássuk mi a helyzet a BFS algoritmussal.
És most lássuk, hogyan is működik itt a BFS algoritmus.
Az algoritms lényege, hogy kiindulunk egy csúcsból…
Aztán megkeressük a közvetlen szomszédjait.
A gráf irányított, ezért a 7-es csúcsba sajna nem vezet él az 1-esből.
Úgy tűnik, hogy két szomszédot találtunk.
Most folytatjuk a keresést, és az új csúcsoknak keressük meg a szomszédjait.
Nagyszerű dolog, hogy a 4-es csúcs mindkét korábbi csúcsnak szomszédja, de ilyenkor csak az egyik élt választjuk.
Mindegy melyiket.
És megyünk tovább…
Hát, ez meg is van.
A BFS algoritmus eredményeként kapjuk a BFS-fát.
Hogyha a BFS-fába berajzoljuk az eredeti gráf többi élét is…
Akkor ezek az élek három típusba sorolhatóak.
Ahogyan korábban a DFS-fánál már láttuk, vannak „előre-él”ek, „vissza-él”ek és „kereszt-él”ek.
Pontosabban csak „vissza-él”ek vannak…
és „kereszt-él”ek.
„Előre-él” nincs.
Ha ugyanis lenne egy „előre-él”…
mondjuk például itt…
Akkor lenne egy közvetlen él a 3-as csúcsból a 6-os csúcsba.
De akkor a 3-as csúcsnak a 6-os is közvetlen szomszédja lenne…
és így hibás lenne a BFS-fa.
Azokban az esetekben, amikor a gráf súlyozott, a BFS algoritmus nem működik.
Ilyenkor a BFS helyett egy másik algoritmus van forgalomban.
Nézzük meg ezt is…
És most nézzük meg, hogyan működik a Dijkstra algoritmus irányított gráfokban.
Az algoritmus lényege, hogy választunk egy pontot…
és ebből a pontból kiindulva csúcsról csúcsra haladva földerítjük az egész gráfot.
Megnézzük, hogy az 1-es csúcs közvetlen szomszédjai milyen távol vannak…
és szépen egyenként beírjuk a táblázatba.
Aztán amelyik csúcsról kiderül, hogy a legközelebb van…
annak a sorszámát beírjuk ide.
És ebből az új csúcsból megyünk tovább.
Megint kiválasztjuk a minimumot…
és a csúcs sorszámát beírjuk szépen ide, ahova kell.
Aztán ebből a csúcsból folytatjuk a felderítést.
Találtunk már ennél rövidebb utat is a 4-es csúcsba…
Úgyhogy ezt most szépen kicseréljük.
Aztán lássuk, mi van itt még…
Kiválasztjuk megint a legkisebbet…
és a csúcs sorszámát beírjuk ide, ahova kell.
Most a 4-es csúcsból folytatjuk a felderítést.
Nagy izgalmak itt nem lesznek.
És megyünk tovább az 5-ös csúcsból.
Végül itt a 7-es.
Hát, volt már jobb is…
A Dijkstra algoritmus távolság szerint felsorolta a gráf csúcsait.
Na persze ez a távolság mindig az 1-es csúcstól mért távolság.
Hogyha kíváncsiak vagyunk két tetszőlegesen kiválasztott csúcs távolságára…
akkor ebben egy újabb algoritmus fog tudni nekünk segíteni.
