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)
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)
def dfs_recursive(graph, node, visited):
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in graph:
dfs_recursive(graph, neighbor, visited)
# Példa gráf
graph = {
0: ,
1: ,
2: ,
3: ,
4: ,
5:
}
visited = set()
print("DFS rekurzívan:")
dfs_recursive(graph, 0, visited)
def dfs_iterative(graph, start):
visited = set()
stack =
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):
if neighbor not in visited:
stack.append(neighbor)
# Példa gráf
graph = {
0: ,
1: ,
2: ,
3: ,
4: ,
5:
}
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
#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) {
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;
}
#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.rbegin(); it != graph.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
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.