Finden von Eulerkreisen mit dem Algorithmus von Hierholzer

[hawkeye78]

Hallo,

ich habe ein zugegebenermaßen etwas merkwürdiges Hobby ich sammele Algorithmen. Nun treibt mich aber ein Algorithmus in den letzten Tagen ein bißchen in den Wahnsinn. Den auch wenn der Ablauf klar, stehe ich vor dem Problem das ich keine Ahnung habe wie ich das ganze performant implementieren kann.
Bei dem Algorithmus handelt es sich um den Algorithmus von Hierholzer[1], dieser findet in einem ungerichteten Graphen einen Eulerkreis[2] indem er den Graphen in mehrere Teilkreise aufspaltet und so jede Kante genau einmal durchläuft. Ich denke von einem beliebigen Knoten ausgehend, einen initialen Kreis zu finden stellt kein Problem da, nun stellt sich bloß die Frage, wie findet man auch alle übrigen enthalten Kreise um auch alle anderen Kanten zu durchlaufen?
Ich habe bereits mit TRex und yeti darüber diskuttiert aber uns fällt einfach keine performante Lösung ein, vielleicht hat sich ja schon jemand damit mal beschäftigt und kann mir einen Tipp geben wie man so etwas am cleversten implementiert. Den auch wenn davon nichts abhält, zählt es doch zu den Dingen denen ich mich ungern geschlagen geben möchte.
Viele Grüsse
Dan


PS
Dank der Büchersuche habe, habe ich bereits eine Lösung gefunden wie man das ganze für gerichtete Graphen angehen kann, leider funktioniert diese Lösung die für jeden Knoten einen weiteren Zeiger verwaltet nicht für ungereichtete Graphen da jeder Knoten "doppelt" vorhanden ist, und man so bereits besuchte Knoten (ich stelle das ganze im moment als Adjazenzliste dar) überspringen müßte...

[1] http://de.wikipedia.org/wiki/Algorithmus_von_Hierholzer
[2] http://de.wikipedia.org/wiki/Eulerkreisproblem

[reox]

mhh frag doch mal bei stackexchange oder so?

Meine Idee dazu wäre das du eine Nachbarschaftssuche machst und die die Knoten in einer Parent List speicherst. So weißt du von welchem Knoten du gekommen bist und hast auch eine Richtung. Also erstmal Kruskal oder Prim laufen lassen (Wobei ich finde, dass Kruskal wesentliche einfacher zum implementieren ist) und einen (M)ST bauen, dann kennst du auch alle Parents und kannst dann den Algo rennen lassen. Bzw noch einfacher einen Algorithmus schreiben der von einem Ausgangspunkt die Nachbarn bestimmt und die Knoten markiert die er besucht hat, etwa so:

Code: Alles auswählen

function n(Knoten x)
  für alle V: v aus N(x):
    if(!v.marked)   
      markiere v;
      set parent v: x;
      n(v);
    fi
  end
end

vlt hilfts ja?

[hawkeye78]

Hallo,

es freut mich zu sehen das noch jemand mein Problem beachtung schenkt. Ich hätte vielleicht dazu schreiben sollen, das ich das Problem mittlerweile gelöst habe. Ich habe dazu einen zweiten zunächst leeren Graphen definiert und dann jeweils die Kanten die ich bereits durch laufen bin, in den zweiten Graphen kopiert, so kann ich dann jeweils nur den Graphen abzüglich der bereits durchlaufenden Kanten betrachten.
Ansonsten stimme ich dir zu das sich der Algorithmus von Kruskal wirklich einfacher implementieren lässt, aber hier komme ich mit meinem Entwurf ohne aus, wobei ich vielleicht mal die Implementierung von dem Algorithmus von Prim auf meine Liste der zu implementieren Algorithmen setzen sollte. Auf jeden Fall vielen Dank für Deine Antwort.
viele grüsse
Dan

[reox]

hehe im prinzip ist die markierung ja auch nichts anderes oder? vermutlich hast du wenn du nur markierst eine bessere laufzeit als beim kopieren, wobei beides wohl in theta(1) liegt...

[hawkeye78]

stimmt