0 Daumen
383 Aufrufe

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.


1111111.png

Avatar von

1 Antwort

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community