Az algoritmus csak akkor alkalmazható, ha az alábbi feltételek teljesülnek: 1. Euler-kör feltétele: Minden csúcs fokszáma páros. 2. Euler-út feltétele: Pontosan két csúcs fokszáma páratlan. - Ezek a páratlan fokszámú csúcsok az út kezdő- és végpontjai lesznek. 3. Összefüggőség: A gráf minden élét el kell érni, vagyis a gráfnak összefüggőnek kell lennie.
A Fleury-algoritmus lépésenként ellenőrzi a gráf összefüggőségét, ezért kevésbé hatékony, mint más algoritmusok, például a Hierholzer-algoritmus.
Fleury(G, start):
aktuális = start
út =
amíg van még él:
ha lehetséges, válassz olyan élt, ami nem szakadékél
ha nincs más választás, válassz bármelyik élt
adjuk hozzá az élt az útvonalhoz
távolítsuk el az élt a gráfból
lépjünk a következő csúcsra
visszatér út
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph.append(v)
self.graph.append(u)
def remove_edge(self, u, v):
self.graph.remove(v)
self.graph.remove(u)
def is_bridge(self, u, v):
visited = set()
def dfs(node):
visited.add(node)
for neighbor in self.graph:
if neighbor not in visited:
dfs(neighbor)
# Számoljuk az összefüggő komponenseket az él eltávolítása előtt
original_components = len(visited)
self.remove_edge(u, v)
# Számoljuk újra az összefüggő komponenseket
visited = set()
dfs(u)
self.add_edge(u, v)
return len(visited) != original_components
def fleury(self, start):
current = start
path =
while any(self.graph.values()):
for neighbor in self.graph:
if not self.is_bridge(current, neighbor) or len(self.graph) == 1:
path.append((current, neighbor))
self.remove_edge(current, neighbor)
current = neighbor
break
return path
# Példa
g = Graph()
edges =
for u, v in edges:
g.add_edge(u, v)
print("Euler-út:", g.fleury(0))
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
class Graph {
int V;
vector<list<int>> adj;
public:
Graph(int V) : V(V), adj(V) {}
void addEdge(int u, int v) {
adj.push_back(v);
adj.push_back(u);
}
void removeEdge(int u, int v) {
adj.remove(v);
adj.remove(u);
}
void dfs(int v, vector<bool>& visited) {
visited = true;
for (int neighbor : adj) {
if (!visited) {
dfs(neighbor, visited);
}
}
}
bool isBridge(int u, int v) {
vector<bool> visited(V, false);
dfs(u, visited);
int initial_component_count = count(visited.begin(), visited.end(), true);
removeEdge(u, v);
fill(visited.begin(), visited.end(), false);
dfs(u, visited);
addEdge(u, v);
int new_component_count = count(visited.begin(), visited.end(), true);
return initial_component_count > new_component_count;
}
void fleury(int start) {
int current = start;
while (true) {
bool found = false;
for (int neighbor : adj) {
if (!isBridge(current, neighbor) || adj.size() == 1) {
cout << current << " -> " << neighbor << endl;
removeEdge(current, neighbor);
current = neighbor;
found = true;
break;
}
}
if (!found) break;
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(3, 0);
g.addEdge(4, 0);
cout << "Euler-út:" << endl;
g.fleury(0);
return 0;
}
A Fleury-algoritmus egyszerű és jól érthető módja az Euler-út vagy Euler-kör megtalálásának. Az algoritmus legnagyobb hátránya, hogy minden él eltávolításakor ellenőrizni kell, hogy az összefüggőség megmarad-e, ami megnöveli az időkomplexitást. Emiatt nagyobb gráfok esetén gyakran helyettesítik a Hierholzer-algoritmussal, amely hatékonyabb. Az algoritmus azonban kiváló oktatási eszköz, mivel szemléletesen mutatja be az Euler-út fogalmát.