Laden...

Pre-, Post- und inorder Traveriserung von Graphen

Erstellt von Hqrtz vor 2 Jahren Letzter Beitrag vor 2 Jahren 377 Views
H
Hqrtz Themenstarter:in
13 Beiträge seit 2021
vor 2 Jahren
Pre-, Post- und inorder Traveriserung von Graphen

Hallo 🙂

Ich habe eine Frage zur Traversierung von Graphen.

Ich kenne die Preorder, Postorder und Inorder Traversierung nur von Bäumen oder Binären Bäumen.
Auch auf vielen Erklärseiten wird geschrieben, dass es sich bei diesen Traversierungen um Traversierungsmöglichkeiten von (Binär) Bäumen handelt.

Kann man diese drei auch auf Graphen, bei denen jeder Knoten mit jedem Verbunden ist o.ä. verwenden?
Für Pre- und Postorder habe ich hier ein Video gefunden, welches dies gut erklärt: https://www.youtube.com/watch?v=_2eDPL-kjIo
Geht dies auch für Inorder oder kann man bei solchen Graphen nur Pre- und Postorder verwenden?
Und wieso werden die drei Algorithmen (sind ja alles eine Form der Tiefensuche) haupsächlich für Bäume erklärt?

Vielen Dank schonmal 🙂

C
2.121 Beiträge seit 2010
vor 2 Jahren

Und wieso werden die drei Algorithmen (sind ja alles eine Form der Tiefensuche) haupsächlich für Bäume erklärt?

Ein Baum ist ein Graph mit vielen Einschränkungen. Es gibt nur genau einen Einstiegspunkt, eine definierte Richtung (Pfeil bei der Verbindung) und keine Zyklen. Beim Binärbaum hat ein Knoten maximal zwei Nachfolger, so dass man von links und rechts sprechen kann und die Nachfolger somit auch geordnet sind (z.B. links ist immer kleiner als rechts).
Ein allgemeiner Graph kann bidirektionale Verbindungen und Zyklen haben und seine Nachfolger haben auch nicht unbedingt eine Sortierung.

Preorder und Postorder besuchen die Nachfolger beim Binärbaum entweder alle vor dem Knoten oder alle nach dem Knoten. Das lässt sich von den zwei Nachfolgern beim Binärbaum leicht auf sonstige Anzahlen an Nachfolgern erweitern. Dann sind es eben nicht zwei Teile die man alle vor/nach dem Knoten besucht, sondern mehr.

Inorder besucht den Knoten genau zwischen dem linken und dem rechten Nachfolgerknoten. Das "zwischen" wird beim beliebigen Graphen schwer, denn der hat nicht nur (maximal) zwei Nachfolger.
Natürlich kannst du dir eine Strategie überlegen die "inorder" funktioniert. Zum Beispiel indem du den Knoten selbst immer nach dem ersten Nachfolgebaum untersuchst (egal wie viele noch kommen), oder immer vor dem vorletzten, oder immer nach der Hälfte oder was dir eben einfällt.

H
Hqrtz Themenstarter:in
13 Beiträge seit 2021
vor 2 Jahren

Ok vielen Dank für die uper Erklärung. Hat mir wirklich sehr weitergeholfen!!

Danke 🙂