Breitensuche und Tiefensuche

Question

Frage:

Verwenden Sie sowohl die Breitensuche (BFS) als auch die Tiefensuche (DFS), um in dem folgenden Graphen die von A erreichbaren Knoten zu bestimmen. Markieren Sie dabei in jedem Schritt die verwendeten Kanten und geben Sie den Inhalt des Stacks bzw. der Queue an. Gehen Sie davon aus, dass die Adjazenzlisten der Knoten in alphabetischer Reihenfolge vorliegen.

Answer 1

Hallo eli-98,

für die Tiefensuche(DFS) in einem ungerichteten Graphen mit Startknoten A und alphabetischer Adjazenzliste, wird begonnen beim Knoten A, der Knoten besucht zu dem es eine Kante gibt, von dort aus der Nächste.... Gibt es mehrere abgehende Kanten wird in diesem Beispiel der Knoten besucht, der alphabetisch als nächstes kommt (durch die alphabetische Adjazenzliste). So werden die Knoten dieses Graphens, mit der DFS, in dieser Reihenfolge exploriert: [ A, B, C, D, E, F, G, H, I, J, K, L]

Bei der Breitensuche (BFS) in einem ungerichteten Graphen mit Startknoten A und alphabetischer Adjazenzliste, werden von A ausgehend alle Knoten exploriert zu denen es von A aus eine Kante gibt (wieder in alphabetischer Reihenfolge). Sind alle Nachbarknoten von A exploriert, werden alle Nachbarknoten exploriert, des Knotens, der nach A als erstes entdeckt wurde (und die bei A noch nicht entdeckt wurden), sind hier alle gefunden, geht es an die Nachbarknoten des Knotens der nach A als zweites entdeckt wurde...., solange bis alle Knoten besucht wurden. BFS: [A, B, C, D, G, E, F, H, J, K, I, L]

Ich hoffe, es ist so weit verständlich.