Tiefensuche


Das angegebene Verfahren zur Markierung eines ungerichteten Graphen entfernt sich vom Startknoten immer möglichst weit, (bei einem Baum würde es jeweils ganz in einen Unterbaum absteigen), daher nennt man es Tiefensuche. Es ist schon aus dem Altertum und aus der griechischen Sage bekannt unter dem Namen Labyrinth-Suche;  das bezieht sich auf die Erzählung von dem griechischen Helden Theseus, der nach Kreta reiste, um dort ein Untier namens Minotauros zu erlegen, das dort in einem unterirdischen Höhlensystem, genannt Labyrinth, sein Unwesen trieb.

Nach einer anderen Lesart war es kein Höhlensystem, sondern der Königspalast von Knossos selbst, in dem man sich in der Tat sehr leicht verlaufen kann; jedenfalls fand Theseus den Minotauros mittels Tiefensuche, und als Markierungshilfsmittel verwendete er das Wollknäuel aus dem Strickzeug der Königstochter Ariadne, mit der er sich angefreundet hatte. Die Sache ging übrigens nicht gut aus: dem König Minos war das Ganze nicht so recht (klassische Schandmäuler behaupten: der Königin noch weniger), und so mußte die beiden jungen Leute rasch aus Kreta verschwinden, vertrugen sich aber dann doch nicht so gut, sodaß Theseus Ariadne auf der Insel Naxos sitzen ließ, wie eine wunderschöne Oper von Richard Strauss erzählt. Ihre Trauer drang bis zu den Göttern im Olymp, und Gott Bacchus soll sie getröstet haben (Skeptiker vermuten, mittels seines berühmten Produktes); und bei der Rückkehr des Theseus aufs griechische Festland ertränkte sich sein Vater auf Grund eines bedauerlichen Mißverständnisses. Man sieht hier sehr schön die ungeheure Tragweite von Informatik-Konzepten, von der Mythologie bis zur spätromantischen abendländischen Musik.

Der Ariadne-Faden markiert übrigens gerade die bisher besuchten Knoten, und da er wieder aufgewickelt wird, verhält er sich wie ein Stack. Wenn wir ihn explizit mitrechnen, bekommen wir einen nichtrekursiven  Algorithmus:

PROCEDURE markiereKomponente(x: Knoten; f: Farbe);
VAR y, z: Knoten; s: STACK OF Knoten;
BEGIN newstack(s); markiereKnoten(x, f); push(s, x);
      WHILE NOT isempty(s)
      DO pop(s, z);
         FOR ALL y IN Nachbarn(z)
         DO IF NOT markiert(y) 
            THEN markiereKnoten(y, f); push(y, f);
            END;
         END;
      END;
END markiereKomponente;

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36