vorige nächste

Probleme bei der Tiefensuche


Wir sind zunächst einmal von einem einfachen gerichteten Graphen ausgegangen. Allerdings stellt unser Beispiellabyrinth die Kanten nicht gerichtet dar. Die Graphen sind aber schon beim Labyrinth - Problem und bei sehr vielen anderen realen Problemen leider nicht gerichtet. Zusätzlich muss man leider in vielen Fällen von einer größeren Zahl von Kanten zwischen den Knoten ausgehen als im einführenden Beispiel.

Unser Beispiellabyrinth wird eher die folgende Form haben:

1 -- 2 -- 3
I   I   I
4 -- 5 -- 6
I   I   I
7 -- 8 -- 9

Warum ist das leider der Fall ? Man hat doch nun viel mehr Möglichkeiten ?

Verfolgen Sie auch für dieses einfache Labyrinth einmal die ersten Schritte der Expansion des Graphen!


Der neue Graph
(define
   Graph
   '( (1 (2 4))
      (2 (1 3 5))
      (3 (2 6))
      (4 (1 5 7))
      (5 (2 4 6 8))
      (6 (3 5 9))
      (7 (4 8))
      (8 (5 7 9))
      (9 (6 8))))