Wikiszótár

Hierholzer-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈhijɛrɦolzɛrɒlɡoritmuʃ]

Főnév

Hierholzer-algoritmus

  1. (matematika, algoritmusok, gráfelmélet)

Hierholzer-algoritmus leírása

A Hierholzer-algoritmus hatékonyan megtalálja az Euler-kört egy gráfban. Az algoritmus az élek iteratív eltávolításával és részutak építésével dolgozik, amelyeket végül egyetlen körrel fűz össze.


Pseudokód (irányítatlan gráfhoz)

Hierholzer(graph):
    1. Válassz ki egy kezdőcsúcsot (bármely csúcs lehet, amelynek van éle).
    2. Hozz létre egy üres veremet (stack) és egy üres listát (circuit).
    3. Tedd a kezdőcsúcsot a stack tetejére.
    4. Amíg a stack nem üres:
        4.1. Ha a stack tetején lévő csúcsnak van éle:
            4.1.1. Válassz egy szomszédos csúcsot.
            4.1.2. Távolítsd el az élt a gráfból.
            4.1.3. Tedd a szomszédos csúcsot a stack tetejére.
        4.2. Egyébként:
            4.2.1. Vedd le a csúcsot a stack tetejéről.
            4.2.2. Add hozzá a circuit listához.
    5. Fordítsd meg a circuit listát, és adja vissza azt.

Python implementáció

Irányítatlan gráf

import networkx as nx

def hierholzer_algorithm(graph):
    # Gráf másolása
    g = graph.copy()
    circuit = []  # A teljes Euler-kör
    stack = [list(g.nodes)[0]]  # Bármely csúccsal kezdhetjük

    while stack:
        current = stack[-1]
        if g.degree(current) > 0:
            # Válassz egy szomszédos csúcsot
            neighbor = next(iter(g.neighbors(current)))
            stack.append(neighbor)
            g.remove_edge(current, neighbor)  # Élt eltávolítjuk
        else:
            circuit.append(stack.pop())  # Kör része lesz ez a csúcs

    return circuit[::-1]  # Megfordítva adja vissza a helyes sorrendet

# Példa gráf
G = nx.Graph()
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
G.add_edges_from(edges)

# Hierholzer algoritmus futtatása
euler_circuit = hierholzer_algorithm(G)
print("Euler-kör:", euler_circuit)

Kimenet:

Euler-kör: [0, 1, 2, 0, 3, 4, 0]

C++ implementáció

Irányítatlan gráf

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <set>
using namespace std;

// Gráf reprezentáció
class Graph {
public:
    unordered_map<int, multiset<int>> adj;

    void addEdge(int u, int v) {
        adj[u].insert(v);
        adj[v].insert(u);
    }

    void removeEdge(int u, int v) {
        adj[u].erase(adj[u].find(v));
        adj[v].erase(adj[v].find(u));
    }
};

vector<int> hierholzer(Graph& graph, int start) {
    stack<int> stack;
    vector<int> circuit;
    stack.push(start);

    while (!stack.empty()) {
        int current = stack.top();
        if (!graph.adj[current].empty()) {
            int neighbor = *graph.adj[current].begin();
            stack.push(neighbor);
            graph.removeEdge(current, neighbor);
        } else {
            circuit.push_back(current);
            stack.pop();
        }
    }

    reverse(circuit.begin(), circuit.end()); // Fordított sorrendben adjuk vissza
    return circuit;
}

int main() {
    Graph g;

    // Gráf élei
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 0);

    // Hierholzer algoritmus futtatása
    vector<int> eulerCircuit = hierholzer(g, 0);

    // Euler-kör kiíratása
    cout << "Euler-kör: ";
    for (int node : eulerCircuit) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Kimenet:

Euler-kör: 0 1 2 0 3 4 0

Összegzés

  • Hierholzer-algoritmus hatékonyan működik Euler-körök keresésére, mivel minden él pontosan egyszer kerül be a körbe.
  • Pythonban a networkx segítségével egyszerűsíthető az implementáció, de a manuális implementáció a gráfok működésének mélyebb megértését szolgálja.
  • C++-ban a multiset-ek használata biztosítja, hogy a szomszédos csúcsok gyorsan és egyenletesen hozzáférhetők legyenek.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Hierholzer-algoritmus&oldid=3480312”