Übung 09

Aufgabe 1

a) DFS-Verfahren

• 1 (Baumkante)
• 3
• 5 (Baumkante)
• 4 (weil das die niedriegste nächste Zahl ist)
• 2
• 8 (Hier ist der Pfad zuende, dementsprechend bekommt die 8 die Fin-Num 1)
• 2 (Wir gehen wieder zurück, und dann bekommt die 2 die Fin-Num 2)
• 7 (Baumkante, weil wir sie vorher nicht besucht hatten)
• 8 (Crosskante (weil die 8 schon besucht wurde, und wir so die etablierte Reihenfolge brechen))
• 7 (Fin-Num 3)
• 4 (Towardkante, Fin-Num 4)
• 5 (Wir gehen weiter zurück)
• 7 (Crosskante)
• 5 (Fin-Num 5)
• 3 (Direkt fertig, da keine "unbenutzten" wege existieren, Fin-Num 6)
• 1
• 5 (Crosskante)
• 1 (Fin-Num 8)
• Jetzt sind wir mit dem ersten teilbaum fertig und fangen beim 2. an (also 6)
• 6
• 7 (crosskante, weil wir die 7 ja schon kennen)
• 6 (Fin-Num 8)
• 9 (Crosskante, Fin-Num 9)
• Topologische Sortierung: 9, 6, 1, 3, 5, 4, 7, 2, 8

b) BFS-Verfahren

flowchart TD 
1 --> 3 
1 --> 5 
3 --> |Cross| 5 
5 --> 4 
5 --> 7
4 --> |Cross| 7
7 --> |Cross| 8
4 --> 2 
4 --> 8 
2 --> |Cross| 8
6 --> |Cross| 7
9 --> |Cross| 6

Aufgabe 2

component:

• Wenn so eine Aufgabe in der Klausur kommt, alles beschreiben was man tut, denn sonst ist es sehr schwer bzw. praktisch unmöglich Teilpunkte zu geben
• Beispielsweise sowas wie:

1. DFS besucht 1, 5, 2 und identifiziert {1, 5, 2} als Komponente. 1 wird als repräsentant ausgewählt
2. DFS besucht 3, 4, 6, 8, 9, 10, 7 in dieser reihenfolge
   1. 6 wird durch kante (9, 6) als Repräsenentat indetifiziert
   2. 10 wird durch kante (7, 10) als Repräsenentat indetifiziert
   3. 7, 10 wird kollabiert
   4. 6, 8, 9 wird kollabiert
   5. 4 wird kollabiert
   6. 3 wird kollabiert