Exkurs - Tiefensuche

Wegsuche mit Ausgaben

Wir betrachten weiterhin die Wegsuche in gerichteten Graphen ohne Kreise und verdeutlichen die Ergebnisse am folgenden Beispielgraphen.

Die folgenden Regeln zur Festlegung des weg-Prädikats benutzen ein zusätzliches print-Prädikat, mit dem während der Auswertung von Anfragen Ausgaben auf dem Bildschirm erzeugt werden können.

% Graph
kante(a, b).
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
% Weg
weg(X, Y) :- kante(X, Y), print(Y).
weg(X, Y) :- kante(X, Z), print(Z), weg(Z, Y).

Aufgabe 1

(a) Teste zunächst die Regeln mit Anfragen wie der folgenden.

?- weg(a, h).
bdgeecefbdgeeih

Yes

Kannst du erklären, wie die Ausgaben zu Stande kommen?

(b) Warum bezeichnet man die Suche hier auch als "Tiefensuche"?

Aufgabe 2

Kann man auch das mit den unten gezeigten Regeln festgelegte weg-Prädikat benutzen, um festzustellen, ob es einen Weg von einem Startknoten X zu einem Zielknoten Y in einem vorgegebenen Graphen ohne Kreise gibt?

% Weg
weg(X, X).
weg(X, Y) :- kante(X, Z), weg(Z, Y).

Teste dieses weg-Prädikat und erkläre die Arbeitsweise.

Aufgabe 3

Warum funktioniert die Tiefensuche mit dem bisher festgelegten weg-Prädikat nicht bei Graphen mit Kreisen? Probiere es ggf. aus, indem du eine zusätzliche Kante im Graphen einführst.