Breitensuche auf Graphen

Die Breitensuche ist ein Verfahren zum Durchsuchen von Graphen. Am Besten stellen Sie sich diesen Graphen als einen Straßenplan vor, dessen Knoten Städte sind.

Man nennt es Breitensuche, weil jede dem Knoten anschließende Kante direkt besucht wird, jedoch kein Ast direkt bis zu seinem Ende weiter verfolgt wird. Die Suche verläuft demnach in die Breite. Mit der Breitensuche kann zu der reinen Objektsuche auch ein kürzester Weg (Anzahl der Kanten) gefunden werden.

Ein denkbarer Algorithmus wäre:

1. Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange ab.
2. Nehme den nächsten Knoten der Warteschlange. Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere *gefunden* zurück. Anderenfalls hänge alle Nachbarn dieses Knotens ans Ende der Warteschlange an, wenn sie nicht schon in der Warteschlange sind.
3. Wenn die Warteschlange abgearbeitet wurde, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere *nicht gefunden* zurück.
4. Wiederhole ab Schritt 2.

Gesucht wird nach dem Namen des Ojektes der gleich dem Gesuchten ist.

• Überlegen Sie sich, wie der Algorithmus diesen Graphen (Abbildung "Netz") durchläuft und nach wieviel Schritten, er das Ziel finden würde (von B nach H).
• Wie könnte eine Implementierung in Matlab aussehen?
• Wie wäre es möglich, zu dem Suchen des Objektes, auch einen Weg zu speichern?

Über die Breitensuche eine Objektsuche zu machen, ist nicht unbedingt sehr effizient. Würde man linear alle Objekte durchsuchen, die existieren, würde man zu schnelleren Ergebnissen kommen, da weniger Vergleiche von Nöten (die gleiche Anzahl von Schritten!!) wären.

Wie müssten Sie Ihren Algorithmus modifizieren, um einen Weg zu dem gesuchten Knoten zu finden? Ist der gefundene Weg der optimale bzw. kürzeste Weg?