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:
- entferne alle Markierungen auf der Halde.
- laufe über alle deklarierten, gültigen
Pointer-Variablen und markiere alle Knoten
des jeweils daran hängenden Geflechtes.
- gib alle nun noch unmarkierten Halden-Objekte zurück.
- vielleicht kann man dabei die Halde noch reorganisieren,
um die weitere Verwaltung zu vereinfachen. Dabei müssen die
betroffenen Pointer-Werte womöglich umgerechnet werden, falls
ihre Bezugsobjekte verlagert wurden.
- ob man Tiefensuche oder Breitensuche zur Markierung verwendet,
ist ein Zweckmäßigkeitsfrage, die durch die Art der geplanten
Reorganisation beeinflußt wird; für die ansonsten korrekte
Funktion spielt die Entscheidung keine Rolle.
Damit dies überhaupt möglich ist, müssen einige
Voraussetzungen erfüllt sein:
- jedes Haldenobjekt muß als solches erkennbar sein.
- für jedes Haldenobjekt muß sein aktueller Typ
feststellbar sein, insbesondere muß feststehen,
welche seiner Felder weitere Pointer enthalten.
- alle Pointer müssen wohldefiniert oder mit NIL besetzt 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