Eulerweg Finder

Pseudocode

Der Existenztest ist reines Zählen und braucht einen Durchlauf. Erst wenn er gelingt, baust du den Weg, und zwar mit Hierholzer statt mit naivem Backtracking.

// Existenz, zusammenhängender ungerichteter Graph:
//   0 Knoten ungeraden Grades -> Eulerkreis
//   2 Knoten ungeraden Grades -> Eulerweg dazwischen
//   alles andere               -> keines von beiden

Hierholzer(graph, start):
    stapel = [start]; weg = []

    solange der Stapel nicht leer ist:
        u = stapel.oben
        wenn u eine unbenutzte anliegende Kante (u,v) hat:
            markiere diese Kante als benutzt
            stapel.push(v)
        sonst:
            weg.anhängen(stapel.pop())

    kehre weg um

Hierholzer funktioniert, weil er nie raten muss. Er läuft, bis er stecken bleibt, was in einem Graphen mit lauter geraden Graden nur am Startknoten passieren kann, und fügt dann Umwege von Knoten ein, die noch unbenutzte Kanten haben. Jeder Knoten wird gleich oft betreten wie verlassen, und genau das garantiert der gerade Grad, sodass die Teilstücke stets zu einem einzigen geschlossenen Weg verschmelzen.

Durchgerechnetes Beispiel, Schritt für Schritt

Baue einen Eulerkreis auf zwei Dreiecken, die sich einen einzigen Knoten teilen, wobei die Nachbarn alphabetisch genommen werden.

Beispielgraph: Ungerichtete Kanten A-B, B-C, C-A bilden ein Dreieck, und C-D, D-E, E-C bilden ein zweites, verbunden über C.

1. Zuerst die Grade prüfen. A hat Grad 2, B hat 2, C hat 4, D hat 2 und E hat 2. Alle Grade sind gerade und der Graph ist zusammenhängend, also existiert ein Eulerkreis und er darf überall beginnen.
2. Laufen, bis es klemmt. Von A aus nimm A-B, dann B-C, und von C aus nimm C-A. Nun bist du zurück bei A, dessen beide Kanten benutzt sind, der Lauf steckt also fest. Beachte, dass er am Startknoten festhing, was gerade Grade unvermeidlich machen.
3. Das zweite Dreieck einfügen. Beim Abwickeln des Stapels erreichst du C, das noch die unbenutzten Kanten C-D und C-E besitzt. Laufe C-D, dann D-E, dann E-C, und nun ist auch C erschöpft.
4. Zum Weg abwickeln. Da nirgends mehr unbenutzte Kanten liegen, leert sich der Stapel der Reihe nach, und das umgekehrte Ergebnis ist der Kreis.

Der Eulerkreis lautet A nach B nach C nach D nach E nach C nach A und benutzt alle sechs Kanten genau einmal, mit Rückkehr zum Start. Beachte, dass C zweimal im Weg vorkommt, was erlaubt und zu erwarten ist: ein Eulerweg darf Knoten beliebig wiederbesuchen, er darf lediglich keine Kante erneut benutzen. Genau darin liegt der Unterschied zu einem Hamiltonweg, der jeden Knoten einmal besucht und sich um Kanten nicht schert.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V + E)

Die Gradzählung ist ein Durchlauf über die Kanten mit O(E), und die Zusammenhangsprüfung ist ein Durchlauf mit O(V + E). Hierholzer legt jedes Knotenvorkommen einmal ab und nimmt es einmal auf und markiert jede Kante genau einmal als benutzt, ist also O(E), sofern jeder Knoten einen Zeiger in seine Adjazenzliste behält statt von vorn zu suchen. Ohne diesen Zeiger degradiert die innere Suche auf O(V·E). Der Speicher besteht aus den Benutztmarkierungen sowie Stapel und Weg, die O(E) Einträge halten. Der Gegensatz zu Hamiltonwegen ist bemerkenswert: Eulersch ist linear, Hamiltonsch ist NP-vollständig, und zwar allein deshalb, weil Kanten sich lokal über den Grad zählen lassen, Knoten aber nicht.

Wann Eulerscher Pfad (Ungerichtet) passt und wann nicht

Eulersche Probleme sind leicht; die oberflächlich ähnlichen hamiltonschen sind es nicht. Prüfe, welches du tatsächlich vor dir hast.

Häufige Fehler

• Die Zusammenhangsbedingung vergessen. Gerade Grade allein genügen nicht. Ein Graph aus zwei disjunkten Dreiecken hat lauter gerade Grade und keinen Eulerkreis, denn kein Weg kann zwischen Komponenten springen. Alle Kanten müssen in einer Zusammenhangskomponente liegen; isolierte Knoten mit Grad null darf man ignorieren.
• Eulersch mit hamiltonsch verwechseln. Eulersch benutzt jede Kante einmal und darf Knoten wiederholen; hamiltonsch besucht jeden Knoten einmal und darf Kanten auslassen. Die Begriffe klingen ähnlich und unterscheiden sich in der Schwierigkeit dramatisch: linear gegen NP-vollständig.
• Adjazenzlisten in Hierholzer erneut durchsuchen. Beginnt die Suche nach einer unbenutzten Kante jedes Mal am Listenanfang, wird der Algorithmus quadratisch. Halte je Knoten einen Iterator, der nur vorwärts läuft, denn eine benutzte Kante ist nie wieder nützlich.
• Die ungerichtete Gradregel auf einen gerichteten Graphen anwenden. Gerichtete Graphen brauchen für einen Kreis an jedem Knoten gleichen Ein- und Ausgangsgrad, oder für einen Weg genau einen Knoten mit Ausgang minus Eingang gleich 1 und einen mit Eingang minus Ausgang gleich 1. Den Gesamtgrad zu zählen liefert die falsche Antwort.
• Einen Weg am falschen Knoten beginnen. Haben genau zwei Knoten ungeraden Grad, muss der Weg an einem beginnen und am anderen enden. Woanders zu starten bedeutet, mit übrig gebliebenen Kanten stecken zu bleiben.

Häufig gestellte Fragen

Was ist ein Eulerweg?

Ein Eulerweg ist ein Weg, der jede Kante eines Graphen genau einmal benutzt. Knoten darf er mehrfach besuchen. Kehrt er zusätzlich zum Startknoten zurück, heißt er Eulerkreis. Die Idee geht auf Euler zurück, der 1736 das Königsberger Brückenproblem löste und damit die Graphentheorie begründete.

Wann existiert ein Eulerweg?

In einem zusammenhängenden ungerichteten Graphen existiert ein Eulerkreis, wenn jeder Knoten geraden Grad hat, und ein Eulerweg, wenn genau zwei Knoten ungeraden Grad haben; dann muss der Weg an einem beginnen und am anderen enden. Jede andere Anzahl ungerader Knoten bedeutet, dass keines von beiden existiert. Alle Kanten müssen zudem in einer einzigen Zusammenhangskomponente liegen.

Was ist der Unterschied zwischen Euler- und Hamiltonwegen?

Ein Eulerweg benutzt jede Kante einmal und darf Knoten wiederbesuchen; ein Hamiltonweg besucht jeden Knoten einmal und darf Kanten ignorieren. Der Unterschied in der Schwierigkeit ist gewaltig: die Existenz eines Eulerwegs entscheidet man in O(V + E) durch Zählen der Grade, die hamiltonsche Frage ist NP-vollständig.

Wie funktioniert der Algorithmus von Hierholzer?

Er läuft über unbenutzte Kanten, bis er stecken bleibt, was in einem Graphen mit geraden Graden nur am Startknoten geschehen kann. Dann wickelt er den Stapel ab, und sobald er einen Knoten mit unbenutzten Kanten findet, läuft er von dort eine neue geschlossene Schleife und fügt sie ein. Das Abräumen des Stapels ergibt den vollständigen Weg in umgekehrter Reihenfolge, und der gesamte Lauf ist O(E).

Wie ist die Zeitkomplexität für das Finden eines Eulerwegs?

O(V + E). Das Zählen der Grade ist O(E), die Zusammenhangsprüfung ein Durchlauf, und Hierholzer markiert jede Kante genau einmal als benutzt. Der entscheidende Implementierungskniff ist ein Zeiger je Knoten in die Adjazenzliste, damit die Suche nach unbenutzten Kanten nie erneut sucht; das hält den Algorithmus linear statt quadratisch.