Algorithmus von Hierholzer

!300
Voraussetzung: $G=(V,E)$ ist zusammenhängend, alle Knoten haben geraden Grad

1. Wähle beliebigen Knoten $v_0$ in $G$. Konstruiere von $v_0$ ausgehend einen Unterkreis $K$ in $G$, der keine Kante in $G$ zweimal durchläuft
2. • Wenn $K$ ein Eulerkreis in $G$ ist, brich ab,
   • sonst: lösche nun alle Kanten des Unterkreises $K$.
3. am ersten Knoten von $K$, dessen Grad größer 0 ist, starte weiteren Unterkreis $K\prime$, der keine Kante in $G$ zweimal durchläuft
4. füge $K\prime$ in $K$ ein, indem der Startknoten von $K\prime$ durch alle Knoten von $K\prime$ in der richtigen Reihenfolge ersetzt wird. Nenne den so erhaltenen Kreis $K$. Fahre bei Schritt 2 fort.