depth-first search (tsz. depth-first searches)
A mélységi keresés (Depth-First Search, DFS) egy alapvető algoritmus gráfok és fák bejárására. A célja, hogy a gráf egy adott csúcsától kiindulva minél mélyebben elérje az összes elérhető csúcsot, mielőtt visszalépne, hogy más elágazásokat is felfedezzen. A DFS-t általában rekurzívan vagy veremben (stack) tárolt csúcsokkal valósítják meg.
A mélységi keresés alapvetően az alábbi lépéseket követi: 1. Kezdi egy adott csúcsot, és azt felfedezi. 2. Az aktuális csúcsról átmegy egy még nem felfedezett szomszédos csúcsra. 3. Ezt addig folytatja, amíg el nem ér egy olyan csúcsot, amelynek már minden szomszédja fel van dolgozva. 4. Visszalép az előző csúcsra, és újra próbálkozik egy másik szomszéddal. 5. A keresés addig tart, amíg minden elérhető csúcsot fel nem dolgoztunk.
Az alábbi C++ kód bemutatja, hogyan valósítható meg a DFS rekurzív módszerrel. Ebben a példában egy irányított gráfot reprezentálunk szomszédsági listával, és az algoritmus a DFS-t alkalmazza a csúcsok bejárására.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
public:
int V; // A csúcsok száma
vector<vector<int>> adj; // Szomszédsági lista
Graph(int V); // Konstruktor
void addEdge(int v, int w); // Él hozzáadása
void DFS(int start); // Mélységi keresés
void DFSUtil(int v, vector<bool>& visited); // Segéd függvény a rekurzív DFS-hez
};
// Konstruktor
Graph::Graph(int V) {
this->V = V;
adj.resize(V);
}
// Él hozzáadása
void Graph::addEdge(int v, int w) {
adj.push_back(w); // v-ből w-be vezető él
}
// Rekurzív DFS segédfüggvény
void Graph::DFSUtil(int v, vector<bool>& visited) {
visited = true; // Megjelöljük a csúcsot, mint látogatott
cout << v << " "; // Kiírjuk a csúcsot
// Bejárjuk az összes szomszédot
for (int i = 0; i < adj.size(); i++) {
int neighbor = adj;
if (!visited) {
DFSUtil(neighbor, visited); // Rekurzívan hívjuk a DFS-t
}
}
}
// Fő DFS függvény
void Graph::DFS(int start) {
vector<bool> visited(V, false); // Látogatott csúcsok tárolása
DFSUtil(start, visited); // Indítjuk a keresést
}
int main() {
Graph g(5); // 5 csúcsú gráf létrehozása
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
cout << "A DFS bejárás eredménye a 0 csúcsról indulva: ";
g.DFS(0); // Indulás a 0 csúcsról
cout << endl;
return 0;
}
V: A csúcsok száma a gráfban.adj: A szomszédsági lista, amely tárolja a gráf csúcsainak szomszédait.addEdge(v, w) hívás azt jelenti, hogy v csúcsból w csúcsba vezető él van.visited tömböt inicializálunk, amely nyilvántartja, hogy mely csúcsokat látogattuk meg már. A keresés a DFSUtil függvény segítségével történik.
A fenti program a következő kimenetet adja, ha a gráf az alábbi élekkel van feltöltve:
0 -> 1, 2 1 -> 3, 4 2 -> (nincs él) 3 -> (nincs él) 4 -> (nincs él)
A DFS bejárás eredménye a 0 csúcsról indulva: 0 1 3 4 2
Ez a kimenet azt mutatja, hogy a DFS algoritmus először a 0-ás csúcsot látogatja meg, majd a 1-es csúcsot, és az összes lehetséges szomszédot felfedez. A keresés során a mélységre koncentrálva először az összes elérhető csúcsot próbálja bejárni, mielőtt visszalépne.
A fenti kód rekurzívan implementálja a DFS-t, de ugyanezt megvalósíthatjuk verem (stack) használatával is, ami nem igényel rekurziót. Az alábbiakban bemutatok egy iteratív megoldást verem használatával:
void Graph::DFSIterative(int start) {
vector<bool> visited(V, false); // Látogatott csúcsok tárolása
stack<int> s; // Verem létrehozása
s.push(start); // A kezdő csúcsot betesszük a verembe
while (!s.empty()) {
int v = s.top(); // Az aktuális csúcs a verem tetején
s.pop(); // Kivesszük a csúcsot a veremből
if (!visited) {
visited = true; // Megjelöljük, hogy ezt a csúcsot már meglátogattuk
cout << v << " "; // Kiírjuk a csúcsot
}
// Az összes szomszédot hozzáadjuk a veremhez
for (int i = adj.size() - 1; i >= 0; i--) {
int neighbor = adj;
if (!visited) {
s.push(neighbor); // A szomszédot betesszük a verembe
}
}
}
}
Ez az iteratív megoldás ugyanazt a logikát követi, mint a rekurzív, de a stack segítségével manuálisan kezeljük a csúcsokat, így elkerüljük a túlméretezett rekurziós hívásokat.