Moin,
ich versuche mich seit ein paar Tagen an der Implementierung von dem Algorithmus von Hierholzer[1] auf einem ungerichteten Graphen. Ich denke den ersten Kreis zu finden stellt kein Problem dar, man beginnt bei einem beliebigen Startknoten und läuft solange durch den Graphen bis man wieder beim Ausgangsknoten angekommen ist. Nun stehe ich allerdings vor dem Problem, wie finde ich einen weiteren Kreis, ich habe in diesem[2] beitrag gelesen, das man einfach die Kanten löschen kann, die man bereits durchlaufen kann und so nach jedem Schritt ein Restgraph übrig bleibt den man weiter durchlaufen kann. Allerdings stelle ich mir jetzt die Frage ob das nicht vielleicht auch irgendwie geschickter geht. Ich würde mich über die eine oder andere Antwort freuen.
Viele Grüsse
Dan
[1] Algorithmus von Hierholzer ? Wikipedia
[2] http://www.java-forum.org/allgemeine-java-themen/93608-hierholzer-algo-eulerweg.html
ich versuche mich seit ein paar Tagen an der Implementierung von dem Algorithmus von Hierholzer[1] auf einem ungerichteten Graphen. Ich denke den ersten Kreis zu finden stellt kein Problem dar, man beginnt bei einem beliebigen Startknoten und läuft solange durch den Graphen bis man wieder beim Ausgangsknoten angekommen ist. Nun stehe ich allerdings vor dem Problem, wie finde ich einen weiteren Kreis, ich habe in diesem[2] beitrag gelesen, das man einfach die Kanten löschen kann, die man bereits durchlaufen kann und so nach jedem Schritt ein Restgraph übrig bleibt den man weiter durchlaufen kann. Allerdings stelle ich mir jetzt die Frage ob das nicht vielleicht auch irgendwie geschickter geht. Ich würde mich über die eine oder andere Antwort freuen.
Viele Grüsse
Dan
[1] Algorithmus von Hierholzer ? Wikipedia
[2] http://www.java-forum.org/allgemeine-java-themen/93608-hierholzer-algo-eulerweg.html