Breitensuche


Betrachtet man die Folge des Stapelinhalte, die beim Ablauf des genannten Verfahrens auftreten, so stellt man fest, daß sie gerade einen Baum beschreiben, dessen Wurzel der Einstiegsknoten ist, und in den der Reihe nach alle Knoten aufgenommen werden, jeder genau einmal. Einen solchen Baum nennt man oft "Spanning Tree" oder auch Gerüst. Er kann für die weitere Bearbeitung des Graphen sehr nützlich sein. Für mehrere Komponenten erhält man entsprechend einen Wald.

Das angegebene nichtrekursive Verfahren zur Tiefensuche in einem ungerichteten Graphen stellt mittels des als Hilfsspeicher verwendeten Stapels sicher, daß jeder Knoten der Komponente genau einmal bearbeitet wird. Die last-in-first-out-  Eigenschaft ist dafür aber gar nicht wesentlich; dasselbe könnte man auch mit einer Schlange erreichen, die analog verwendet wird (ersetze die Operationen sinngemäß!). Nun ist immer noch sicher, daß jeder Knoten genau einmal zur Bearbeitung herangezogen wird, aber die Reihenfolge ist anders: der neue Algorithmus bleibt solange wie möglich in der Nähe des Startknotens, er heißt Breitensuche.

Für beide Verfahren gibt es wichtige Anwendungen. Eine davon ist die bereits früher angesprochene Speicherbereinigung (Garbage Collection) auf der Halde. Hier geht es darum, alle noch erreichbaren Haldenobjekte aufzufinden und den Rest an die Verwaltung zurückzugeben. Dies findet in mehreren Phasen statt:

Damit dies überhaupt möglich ist, müssen einige Voraussetzungen erfüllt sein: Diese Bedingungen sind leider nicht in allen Programmiersprachen erfüllt, in denen es Pointer gibt; für manche Sprachen ist daher eine automatische Speicherbereinigung nicht möglich. Umgekehrt ist sie für Sprachen unverzichtbar, die mit Haldenobjekten arbeiten, aber gar keine explizite Freigabe anbieten; dazu gehören wichtige objektorientierte Sprachen, aber auch LISP und PROLOG.


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36