Fleury-algoritmus
Kiejtés
- IPA: [ ˈflɛuriɒlɡoritmuʃ]
Főnév
- (matematika, gráfelmélet, algoritmusok) A Fleury-algoritmus egy gráfelméleti algoritmus, amelyet Euler-út vagy Euler-kör megtalálására használnak egy irányítatlan gráfban. Az Euler-út olyan út a gráfban, amely minden élt pontosan egyszer érint. Az Euler-kör ugyanez, azzal a kitétellel, hogy az út ugyanabban a csúcsban kezdődik és végződik.
Elméleti feltételek
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.
Algoritmus működése
Fő lépések:
- Indulás:
- Ha Euler-kört keresünk, kezdjük egy tetszőleges csúcsnál.
- Ha Euler-utat keresünk, kezdjük a páratlan fokszámú csúcsok egyikénél.
- Élek kiválasztása:
- Mindig egy olyan élt válasszunk, amely nem szakadékél (bridge), kivéve, ha nincs más lehetőség. Egy él szakadékél, ha eltávolításával a gráf összefüggősége megszűnik.
- Élek eltávolítása:
- Az aktuális él feldolgozása után töröljük azt a gráfból, és lépjünk a következő csúcsra.
- Ismétlés:
- Addig folytassuk, amíg minden él feldolgozásra nem került.
Fontos megfigyelés:
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.
Pszeudokód
Fleury(G, start): aktuális = start út = [aktuális] 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
Python implementáció
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def remove_edge(self, u, v):
self.graph[u].remove(v)
self.graph[v].remove(u)
def is_bridge(self, u, v):
visited = set()
def dfs(node):
visited.add(node)
for neighbor in self.graph[node]:
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[current]:
if not self.is_bridge(current, neighbor) or len(self.graph[current]) == 1:
path.append((current, neighbor))
self.remove_edge(current, neighbor)
current = neighbor
break
return path
# Példa
g = Graph()
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (3, 0), (4, 0)]
for u, v in edges:
g.add_edge(u, v)
print("Euler-út:", g.fleury(0))
C++ implementáció
#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[u].push_back(v);
adj[v].push_back(u);
}
void removeEdge(int u, int v) {
adj[u].remove(v);
adj[v].remove(u);
}
void dfs(int v, vector<bool>& visited) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
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[current]) {
if (!isBridge(current, neighbor) || adj[current].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;
}
Összegzés
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.
Fordítások
- Fleury-algoritmus - Értelmező szótár (MEK)
- Fleury-algoritmus - Etimológiai szótár (UMIL)
- Fleury-algoritmus - Szótár.net (hu-hu)
- Fleury-algoritmus - DeepL (hu-de)
- Fleury-algoritmus - Яндекс (hu-ru)
- Fleury-algoritmus - Google (hu-en)
- Fleury-algoritmus - Helyesírási szótár (MTA)
- Fleury-algoritmus - Wikidata
- Fleury-algoritmus - Wikipédia (magyar)