Wikiszótár

mélységi keresés

Magyar

Kiejtés

  • IPA: [ ˈmeːjʃeːɡikɛrɛʃeːʃ]

Főnév

mélységi keresés

  1. (matematika, informatika, gráfelmélet, algoritmusok) A mélységi keresés (DFS) egy gráfkeresési algoritmus, amely egy gráf csúcsait mélységi sorrendben járja be. Az algoritmus elindul egy kezdőcsúcsból, és addig halad egy irányba, amíg már nincs további lehetőség. Ezután visszalép az előző csúcsra, és folytatja a keresést.


Algoritmus működése

  1. Kezdés:
    • A kiinduló csúcsot jelöljük látogatottként.
  2. Lépés:
    • Haladjunk tovább egy szomszédos csúcs felé, amelyet még nem látogattunk meg.
  3. Visszalépés:
    • Ha elértük egy út végét (nincs látogatatlan szomszédos csúcs), térjünk vissza az előző csúcsra.
  4. Ismétlés:
    • Addig folytatjuk, amíg minden elérhető csúcsot be nem jártunk.

Adatszerkezet:

  • A DFS tipikusan rekurzióval vagy egy verem (stack) adatszerkezettel valósítható meg.


Tulajdonságok

  • Időkomplexitás: (O(V + E)), ahol (V) a csúcsok száma, (E) az élek száma.
  • Térkomplexitás:
    • Rekurzív megvalósítás: (O(V)) a rekurzív hívások miatt.
    • Iteratív megvalósítás: (O(V)) a verem miatt.
  • Alkalmazások:
    • Összefüggő komponensek meghatározása.
    • Körök észlelése.
    • Topologikus rendezés.
    • Útvonal keresése.


Pszeudokód

Rekurzív változat

DFS(G, v):
    jelöld v-t látogatottként
    minden szomszéd u esetén:
        ha u nincs látogatottként jelölve:
            DFS(G, u)

Iteratív változat

DFS(G, v):
    verem = üres
    verem.push(v)

    amíg verem nem üres:
        u = verem.pop()
        ha u nincs látogatottként jelölve:
            jelöld u-t látogatottként
            minden szomszéd w esetén:
                ha w nincs látogatottként jelölve:
                    verem.push(w)

Python implementáció

Rekurzív változat

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

# Példa gráf
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1, 5],
    5: [4]
}

visited = set()
print("DFS rekurzívan:")
dfs_recursive(graph, 0, visited)

Iteratív változat

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            # Hozzáadjuk a szomszédokat a veremhez (fordított sorrendben a logikus sorrendért)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

# Példa gráf
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1, 5],
    5: [4]
}

print("DFS iteratívan:")
dfs_iterative(graph, 0)

Kimenet mindkét esetben (a példagráftól függően): 

DFS rekurzívan:
0 1 3 4 5 2

DFS iteratívan:
0 1 3 4 5 2

C++ implementáció

Rekurzív változat

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void dfs_recursive(const vector<vector<int>>& graph, int node, unordered_set<int>& visited) {
    if (visited.find(node) == visited.end()) {
        cout << node << " ";
        visited.insert(node);
        for (int neighbor : graph[node]) {
            dfs_recursive(graph, neighbor, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2}, {0, 3, 4}, {0}, {1}, {1, 5}, {4}
    };

    unordered_set<int> visited;
    cout << "DFS rekurzívan:" << endl;
    dfs_recursive(graph, 0, visited);

    return 0;
}

Iteratív változat

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

void dfs_iterative(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> s;

    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (visited.find(node) == visited.end()) {
            cout << node << " ";
            visited.insert(node);

            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (visited.find(*it) == visited.end()) {
                    s.push(*it);
                }
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2}, {0, 3, 4}, {0}, {1}, {1, 5}, {4}
    };

    cout << "DFS iteratívan:" << endl;
    dfs_iterative(graph, 0);

    return 0;
}

Kimenet mindkét esetben: 

DFS rekurzívan:
0 1 3 4 5 2

DFS iteratívan:
0 1 3 4 5 2

Összegzés

A mélységi keresés (DFS) hatékony és egyszerű módszer gráfok bejárására. Széles körben alkalmazzák összefüggő komponensek meghatározására, körök keresésére, topologikus rendezésre és útvonalak felfedezésére. A rekurzív változat olvashatóbb, de nagy gráfok esetén az iteratív megközelítés jobb, mert elkerüli a túlmély rekurzív hívásokat.


Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=mélységi_keresés&oldid=3479476”