Prüfungsfrage 08 – Tiefensuche am Beispiel

 

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:

inginf-kantenliste

Damit erhält man folgenden Graphen:

inginf-tiefensuche

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

inginf-tiefensuche-breitensuche-tabellen