TraversalAlgorithmen

TraversalAlgorithmen sind Algorithmen zur systematischen Besichtigung der Knoten einer Datenstruktur wie Graphen oder Bäumen. Ziel ist es, jeden relevanten Knoten mindestens einmal zu erreichen, wobei die Reihenfolge der Besuche je nach Struktur und Anwendungsfall variiert.

Bei Graphen dominieren Tiefensuche (DFS) und Breitensuche (BFS). DFS vertieft sich Pfade so weit wie möglich, oft rekursiv oder mit einem Stack. BFS verwendet eine Queue und entdeckt Knoten schichtweise. Beide Grundtypen laufen in Zeit O(V+E) und benötigen Speicher O(V) bei Adjazenzlisten.

Bei Bäumen gelten speziellere Traversierungen: Preorder, Inorder und Postorder für binäre Bäume sowie Level-Order für allgemeine Bäume. Diese Reihenfolgen liefern unterschiedliche Nutzungen, etwa Inorder mit sortierter Ausgabe in Binärbäumen (BST) oder das Evaluieren von Ausdrucksbäumen. Die Laufzeit beträgt O(n) und der Platzbedarf O(h) bzw. O(n) beim rekursiven Ansatz.

Anwendungen und Eigenschaften: Traversierungen dienen der Konnektivitätsprüfung, der Pfadsuche, der Zyklenerkennung (mit DFS) sowie der Topologischen Sortierung in gerichteten Graphen. Bei Zyklen müssen Besuche markiert werden, um Mehrfachbesuche zu vermeiden. Für gewichtete oder kürzeste Pfade eignen sich oft andere Algorithmen, Traversierungen dienen dort eher als Bausteine.