Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Pre-, Post- und inorder Traveriserung von Graphen
Hqrtz
myCSharp.de - Member



Dabei seit:
Beiträge: 13

Themenstarter:

Pre-, Post- und inorder Traveriserung von Graphen

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
chilic
myCSharp.de - Experte



Dabei seit:
Beiträge: 2132

beantworten | zitieren | melden

Zitat
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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von chilic am .
private Nachricht | Beiträge des Benutzers
Hqrtz
myCSharp.de - Member



Dabei seit:
Beiträge: 13

Themenstarter:

beantworten | zitieren | melden

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

Danke
private Nachricht | Beiträge des Benutzers