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.
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.
import networkx as nx
def hierholzer_algorithm(graph):
# Gráf másolása
g = graph.copy()
circuit = # A teljes Euler-kör
stack = ] # Bármely csúccsal kezdhetjük
while stack:
current = stack
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 # Megfordítva adja vissza a helyes sorrendet
# Példa gráf
G = nx.Graph()
edges =
G.add_edges_from(edges)
# Hierholzer algoritmus futtatása
euler_circuit = hierholzer_algorithm(G)
print("Euler-kör:", euler_circuit)
Euler-kör:
#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.insert(v);
adj.insert(u);
}
void removeEdge(int u, int v) {
adj.erase(adj.find(v));
adj.erase(adj.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.empty()) {
int neighbor = *graph.adj.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;
}
Euler-kör: 0 1 2 0 3 4 0
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.multiset-ek használata biztosítja, hogy a szomszédos csúcsok gyorsan és egyenletesen hozzáférhetők legyenek.