TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 27

Führen Sie auf dem untenstehenden Graphen den Tiefensuche Algorithmus zum Finden von Kreisen in einem Graphen aus (Algorithmus 34 Depth-First-Search3, Seite 119). Verwenden Sie den Knoten 1 als Startknoten. Die Nachbarn eines Knotens werden immer in aufsteigend sortierter Reihenfolge betrachtet.

Geben Sie an, in welcher Reihenfolge die Knoten jeweils besucht werden und welche Kreise der Algorithmus findet. Geben Sie einen beliebigen Kreis des Graphen an, der nicht vom Algorithmus gefunden wurde.

Lösung

Reihenfolge bei der DFS-Suche: 1-3-2-5-6-4-7-8

gefundene Kreise

• 3-2-5-6-5-3
• 1-3-2-5-6-4-1
• 5-6-7-8-5
• 6-7-8-6

nicht gefundene Kreise

• 1-3-6-4-1
• 1-3-2-5-8-7-6-4-1
• 5-6-8-5
• 1-3-2-5-8-6-4-1
• 3-2-5-8-7-6-3
• 3-2-5-8-6-3