Suchalgorithmen

Suchalgorithmen dienen dazu, Objekte in Datenstrukturen zu finden. Je nachdem, wie diese Struktur vorliegt, kann dann ein Algorithmus besser oder schlechter für die Situation geeignet sein. Der einfachste Fall wäre, dass die Objekte in Form eines Vektors nebeneinander oder untereinander stehen. Angenommen es sind n Objekte vorhanden, dann muss das Programm bei einem linearen Suchalgorithmus im schlimmsten Fall n Objekte besuchen, um ein Bestimmtes zu finden.

Die Objekte werden in der Informatik als Knoten, die Verbindungen zwischen Ihnen als Kanten bezeichnet. Ist diese Struktur nur in eine Richtung verlaufend, spricht man von einer Liste (Vektor). Liegt die Struktur beliebig vor, spricht man von einem Graphen. Sind die Kanten mit Wertigkeiten versehen, ist der Graph gewichtet, sonst nennt man ihn ungewichtet. Ist mit den Kanten eine Richtung vorgegeben, so ist der Graph gerichtet, andernfalls ungerichtet.

Eine Sonderform des Graphen ist ein Baum. Er unterscheidet sich von dem Graphen dadurch, dass er nur in eine Richtung Verzweigungen besitzt und keine Querverbindungen zwischen einzelnen Ästen hat. (Siehe Beispiel)

Ob ein Algorithmus für eine Datenstruktur geeignet ist, lässt sich durch statistische Formeln abschätzen. Man unterscheidet dabei zwischen Speicherplatzverbrauch, Laufzeit, Vollständigkeit und Optimalität:

• Speicherplatzverbauch - Ein Algorithmus ist eventuell schneller, wenn viele Daten zwischengelagert werden. Je nach Größe der untersuchten Struktur, kann das zu enormen Speicherplatzbedarf führen.
• Laufzeit - Ein endlicher Graph soll in möglichst kurzer Zeit durchlaufen werden. An dieser Stelle zeigt sich am deutlichsten die Qualität eines Algorithmus.
• Vollständigkeit - Ein Algorithmus sollte in der Lage sein, jeden Knoten zu besuchen. Tut er das, wird er als vollständig bezeichnet.
• Optimalität - Ein Algorithmus ist optimal, wenn er kosteneffizient arbeitet. Wenn Kantengewichte vorhanden sind, wird der günstigste bzw. leichteste Weg als optimal bezeichnet.