Kiejtés

  • IPA: [ ˈflɛuriɒlɡoritmuʃ]

Főnév

Fleury-algoritmus

  1. (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:

  1. 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.
  2. É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.
  3. É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.
  4. 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