depth-first search

Angol

Főnév

depth-first search (tsz. depth-first searches)

1. (informatika) mélységi keresés

---

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.

DFS rekurzívan

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.

Kód:

#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[v].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[v] = 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[v].size(); i++) {
        int neighbor = adj[v][i];
        if (!visited[neighbor]) {
            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;
}

Magyarázat:

1. Graph osztály:
   • 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.
2. addEdge függvény:
   • Egy irányított élt ad hozzá a gráfhoz. Az addEdge(v, w) hívás azt jelenti, hogy v csúcsból w csúcsba vezető él van.
3. DFSUtil függvény:
   • Ez a rekurzív segédfüggvény végzi el a mélységi keresést. Miután egy csúcsot meglátogatunk, a függvény rekurzívan hívja magát minden olyan szomszédos csúcsra, amelyet még nem látogattunk meg.
4. DFS függvény:
   • Az első híváskor egy 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.

Kimenet példa:

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.

DFS verem (stack) alapú megoldás

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[v]) {
            visited[v] = 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[v].size() - 1; i >= 0; i--) {
            int neighbor = adj[v][i];
            if (!visited[neighbor]) {
                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.

Összegzés:

• A DFS (mélységi keresés) algoritmus segítségével minden csúcsot elérhetünk egy gráfban.
• A DFS megvalósítható rekurzívan vagy iteratívan verem (stack) használatával.
• A rekurzív megoldás egyszerű és könnyen érthető, míg az iteratív megoldás nagyobb kontrollt ad a programozónak, és elkerüli a túlméretezett rekurziós hívásokat.

További információk

• depth-first search - Szótár.net (en-hu)
• depth-first search - Sztaki (en-hu)
• depth-first search - Merriam–Webster
• depth-first search - Cambridge
• depth-first search - WordNet
• depth-first search - Яндекс (en-ru)
• depth-first search - Google (en-hu)
• depth-first search - Wikidata
• depth-first search - Wikipédia (angol)