A mélységi keresés (angolul Depth-first search, DFS) egy hasznos ún. gráfbejárási algoritmus, melynek célja a teljes gráf feltérképezése valamilyen szempont alapján. A gyűjtött adatokból következtetéseket vonhatunk le a gráffal kapcsolatban és ez hétköznapi problémák megoldására is felhasználható.
A bevezetés lehet, hogy egy kicsit komolyra sikerült, de való igaz amit írtam: a gráfbejárás felhasználható „egyszerű”, mindennapos bonyodalmak leküzdésére. Például ahhoz, hogy a lehető leggyorsabb útvonalon menjünk a munkahelyünkre vagy iskolánkba, ezt teszi a Google Térkép is. Hogyan is működik a DFS?
A gráf fogalma (matematika)
A matematikában gráfnak nevezzük a pontok és élek halmazát, ahol a pontokat élek köthetik össze, ezáltal hálózatot alkotnak. Lehetnek egyedülálló pontok és ponthalmazok is, ha van ilyen, akkor nem összefüggő gráfról beszélünk (egyébként összefüggő).
Mélységi keresés
A mélységi keresés legfontosabb tulajdonsága, hogy egy általunk kiválasztott pontból indul és addig megy, amíg csak tud. Ha már nem talál új útvonalat „visszalépeget” az eddig útvonalon mindaddig, amíg nem talál új utat, nem meglátogatott csúcsot. A gráf bejárása által meg tudjuk mondani a gráf komponenseit, vagyis a nem összefüggő részeit, illetve megkaphatjuk, hogy egy fagráfban milyen messze van akármelyik i. pont a kiindulóponttól.
A DFS bejárás az alábbiak szerint jár el:
- Kiválasztjuk a kezdőpontot. Innen kezdődik a bejárás. Ezt a csúcsot nevezzük el currentnek, vagy jelenleginek.
- Bejárás:
- Egy tömbben tároljuk, hogy mely csúcsokat érintettük már, ugyanis nem szeretnénk többször ugyanabba a csúcsba jutni, mert az végtelen hurkot eredményezne. Nevezzük ezt visitednek, ami igaz-hamis értékeket tárol minden csúcsra. Kezdetben minden érték hamis.
- Végigiterálunk (egyenként végigmegyünk) a jelenlegi csúcs szomszédjain
- Ha a jelenlegi csúcs i. szomszédját még nem látogattuk meg, elmentjük meglátogatottnak, majd végrehajtjuk a második lépést az adott szomszédra. Fontos megjegyezni, hogy miután bejártuk a szomszédot, az előző elem folytatja a szomszédjainak ellenőrizését.
- Amennyiben egy fát térképezünk fel, és szeretnénk tudni, hogy az egyes csúcsok milyen messze vannak valamelyik elemtől (például a gyökértől), tehát hány lépésnyi eljutni oda. Ezt megtehetjük úgy, hogy mindig a következő csúcsot (a szomszédot) a jelenlegi csúcs száma + 1-gyel címkézzük fel.
Fa fogalma (matematika)
A matematikában fának nevezzük azt a gráfot, amelynek „bármely két csúcsát pontosan egy út köti össze”, tehát egyféleképpen lehet eljutni. Ezek a gráfok összefüggőek és hurokmentesek. Gyökérnek a fa azt az elemét nevezhetjük, amelynek nincsen szülőeleme, ő áll a hierarchia csúcsán. További információ.
Hogyan működik ez a gyakorlatban?
Tegyük fel, hogy a DFS-t a 3-as csúcsból szeretnénk indítani:
Az algoritmus sorban végigjárja a jelenlegi csúcs szomszédjait. A sorban alatt azt értem, hogy egyesével, nem párhuzamosan – és ez fontos dolog, más algoritmusnál még ez előkerül. Az egyszerűség kedvéért balról jobbra fogom körbejárni a szomszédokat.
Tehát, nézzük a négyes csúcsot! Minden szomszédot bejárunk, járjuk be ezt is! A DFS algoritmus mintha újrakezdődne a négyes csúcsban: megnézzük a szomszédjait. Ebből csak egy van: a hármas csúcs. Ezt már érintettük, az érintetteket vastaggal kiemelem (➜ „megjegyzem, elmentem”). A négyes csúcs bejárása befejeződött, visszalépünk egyet a hierarchiában.
Ismét a hármas csúcsnál vagyunk. Megnézzük a második szomszédját: ez az 5-ös. Járjuk be! Vegyük sorjába a szomszédjait! Ezek: 2-es, 3-as, 6-os, 1-es. Kezdjük a kettessel!
A 2-es csúcs szomszédjai: 5-ös, 6-os. Vizsgáljuk meg az 5-öset! Nem jó, már meglátogattuk. A 6-os csúcs? Az jó lesz! Küldjünk rá DFS-átkot!
A 6-os csúcsnak ezek a szomszédjai: 2-es, 5-ös, 1-es. A 2-es csúccsal mi a helyzet? Meglátogattuk már. Az 5-ös csúccsal? Azt is. Az egyes csúcs azonban nagyszerű lesz.
Az egyes csúcsot vizsgáljuk. Sajnos azonban minden szomszédját már érintettük, végtelen hurkot pedig nem szeretnénk létrehozni (végtelen ideig futna a programunk…). Igen ám, de nem fejeztük be! Nem ellenőriztünk minden utat, például az 5-ös elemnél nem iteráltunk végig minden szomszédján. Visszatérünk a szülőelemhez, a 6-oshoz.
A hatosnál már mindent végrehajtottunk, befejeztük a bejárást. Visszalépünk a 2-esre.
A kettes csúcsban már elvégeztük az ellenőrzést korábban, vagyis bejártuk. Ellenőrizzük az 5-öset!
Az 5-ös csúcsot még nem jártuk be teljesen, nem néztük meg a hatosat és az egyeset. De most, hogy itt tartunk, észrevesszük, hogy ezeket már valaki felderítette, így nem jöhetnek szóba. A bejárást befejeztük.
Most a hármas csúcsnál vagyunk. Két szomszédot nem ellenőriztünk még: az egyeset és a heteset. Mint látjuk, az egyest már bejártuk, a hetest azonban nem. Látogassuk meg!
Megjelöltük a hetes csúcsot. Ennek egy szomszédja van, a hármas. Ezt már meglátogattuk. A hetes bejárását ezzel befejeztük, így visszalépünk a hármasra.
A hármas csúcson végigiteráltunk már, és mivel ez volt a kezdőpont, befejeztük a DFS algoritmust, bejártuk a fát! Várjunk… ezt a tudást mégis hol hasznosíthatom?
A DFS algoritmus alkalmazása
A gráfbejárási algoritmusokat a legkülönbözőbb alkalmakkor hasznosíthatjuk. A DFS algoritmussal hálózat elemzést hajthatunk végre, megtalálhatjuk, hány komponens (nem összefüggő rész) van a gráfban (azáltal, hogy minden nem érintett csúcsra meghívjuk a DFS algoritmust), megnézhetjük vannak-e hurkok a gráfban. Az ilyen algoritmusok alkalmazhatóak hálózattudomány és számítástechnika terén is, sőt, egyes bonyolultabb algoritmusok, mint amilyen például a Dijkstra vagy az A* (ejtsd: „Á csillag” vagy „A star”) algoritmus, képesek megtalálni a legrövidebb utat két csomópont között egy súlyozott gráfban, ahol a gráf élei nem egyenlőek, tehát A-ból B-be például 5 perc eljutni, míg B-ből C-be 12 perc. Így a Google Maps vagy más térképek is használnak ilyeneket.
Hamarosan érkeznek új cikkeim más gráfalgoritmusokról, többek közt a BFS-ről! További jó napot!
C++ kód a DFS algoritmushoz
#include <bits/stdc++.h> // alap fejléc mindenféle modul használatához
using namespace std;
bool answer = true;
void dfs(vector<vector<int>>& g, vector<bool>& visited, int current) {
for (int i = 0; i < (int) g[current].size(); i++) {
if (!visited[g[current][i]]) { // ha nem látogattuk még meg a szomszédot...
visited[g[current][i]] = true; // beállítjuk érintettnek (visited-nek) a szomszédot
dfs(g, visited, g[current][i]);
}
}
}
int main() {
int n, m; cin >> n >> m; // n csomópontból (csúcsból) és m élből álló gráf
vector<vector<int>> g(n);
// ⬆⬆⬆ n elemű gráf, minden elemhez vektor van rendelve a szomszédaival felcímkézve
for (int i = 0; i < m; i++) {
int a, b; // két egymással szomszédos csúcs
cin >> a >> b; // beolvasás
a--; b--;
// ⬆⬆⬆ a két csúcs sorszámának csökkentése, amennyiben az inputban 1-től vannak indexelve
g[a].push_back(b); // a-nak szomszédja b
g[b].push_back(a); // b-nek szomszédja a
}
vector<bool> visited(n); // n elemű visited vektor, kezdetben minden hamis
dfs(g, visited, 0); // bejárjuk a 0-ás elem komponensét
return 0;
}
