Breitensuche (BFS) Tiefensuche (DFS)

Question

Text erkannt:

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

BFS = {"Starting node 1", 2, 3, 4, 7, 5, 6, 8, 10, 11, 9, 12}

DFS = {"Starting node 1", 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

https://www.geogebra.org/m/yvrrvbxp

 \(\scriptsize Adj \, :=  \, \left(\begin{array}{rrrrrrrrrrrr}0&1&1&1&0&0&0&0&0&0&0&0\\1&0&1&1&0&0&1&0&0&0&0&0\\1&1&0&1&0&0&1&0&0&0&0&0\\1&1&1&0&1&0&0&0&0&0&0&0\\0&0&0&1&0&1&0&0&0&1&1&0\\0&0&0&0&1&0&1&1&0&1&0&0\\0&1&1&0&0&1&0&1&0&0&0&0\\0&0&0&0&0&1&1&0&1&1&0&0\\0&0&0&0&0&0&0&1&0&1&0&1\\0&0&0&0&1&1&0&1&1&0&1&0\\0&0&0&0&1&0&0&0&0&1&0&1\\0&0&0&0&0&0&0&0&1&0&1&0\\\end{array}\right)\)