Auf dem Beiblatt ist die rechnerorientierte Darstellung eines Graphen als Kantenliste angegeben. Zeichnen Sie den Graphen und geben Sie an, in welcher Reihenfolge die Knoten des Graphen aufgefunden werden, wenn man, ausgehend vom Knoten A, eine Tiefensuche durchführt.

Lösung

Sei folgende Kantenliste gegeben:

Damit erhält man folgenden Graphen:

Mit Hilfe der Tiefensuche (LiFo) ermittelt man nun die Reihenfolge, in der die Knoten gefunden werden: