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;