Zwiebelschalen Algorithmus


Der Zwiebelschalen Algorithmus arbeitet in zwei Phasen.
Wie der Name bereits erahnen lässt, schält der Algorithmus den Graph, wie eine Zwiebel, von außen nach innen ab.

Erste Phase:

1.Schritt:
Wähle einen Startknoten

2.Schritt:
Gehe von diesem Knoten aus entlang noch unmarkierter Kanten,bis ein Knoten erreicht wird,
von dem keine unmarkierten Kanten mehr ausgehen.

Bemerkung:
Kanten die noch nicht in einem Kantenzug vorkommen, nennt unmarkierte Kanten.

3.Schritt:
Prüfe, ob bereits alle Kanten markiert sind. Ist dies nicht der Fall,
dann suche einen Knoten, von dem noch unmarkierte Kanten ausgehen und wiederhole Schritt 2.
Falls bereits jetzt schon alle Kanten markiert sind gehe direkt zu Schritt 4 über.

Zweite Phase:

4.Schritt:
Setze die Eulertour aus den markierten Kreisen zusammen.
Gehe entlang des ersten Kreises, bis er einen neuen Kreis berührt.
Folge dem neuen Kreis, bis dieser wieder einen berührt, usw..
Wenn alle Kreise markiert sind, gehe den zuletzt begonnenen Kreis zu ende
und dann wieder in den vorherigen hinein und so weiter, bis alle Kanten besucht wurden.