Hallo,
ich habe wieder eine Aufgabe die mir Schwierigkeiten bereitet und hoffe, dass mir jemand einen Schubser in die richtige Richtung gibt.
Gegeben sei der Pseudocode mit G = Graph. G = (V,E) und s = Startknoten:
welcher nun modifiziert wird, indem in der letzten Zeile der Funktion DFS1
eingefügt wird.
Wie oft tritt nun der Fall ein, dass DFS1 keinen weiteren Rekursionsaufruf tätigt, wenn dieser modifizierte Algorithmus (also DFS mit beliebigen Startknoten) auf den vollständigen ungerichteten Graphen (d.h. von jedem Knoten existiert eine Kante zu allen anderen Knoten) mit 15 Knoten ausgeführt wird?
Ich verstehe das für den unmodifizierten Code so:
Für einen ungerichteten Graphen A,B,C (im Dreieck gezeichnet) wird der Startwert A gewählt. A wird auf true gesetzt. Anschließend werden aller Nachbarn von A untersucht, in diesen Fall B. Wenn ein Nachbar auf false gesetzt ist, wird DFS1 nochmals aufgerufen und somit wird auch B true. Im nächsten Schritt wäre dann C dran.
So weit so gut. Für den modifizierten Code, ändert sich doch kaum was außer das im letzen Schritt C wieder auf false gesetzt wird, weil A ja schon besucht wurde. Stimmt das so weit?
Wenn ich das dann richtig verstehe, wird
nur einmal aufgerufen und zwar dann, wenn alle Nachbarn besucht wurden.
ich habe wieder eine Aufgabe die mir Schwierigkeiten bereitet und hoffe, dass mir jemand einen Schubser in die richtige Richtung gibt.
Gegeben sei der Pseudocode mit G = Graph. G = (V,E) und s = Startknoten:
Code:
DFS(G,s):
Discovered[v] <- false für alle Knoten v aus V
DFS1(G,s)
DFS1(G,u):
Discovered[u] <- true
Führe Operation auf u aus (z.B. Ausgabe)
foreach Kante (u, v) inzident zu u
if !Discovered[v]
DFS1(G,v)
welcher nun modifiziert wird, indem in der letzten Zeile der Funktion DFS1
Code:
Discovered[u] <- false
Wie oft tritt nun der Fall ein, dass DFS1 keinen weiteren Rekursionsaufruf tätigt, wenn dieser modifizierte Algorithmus (also DFS mit beliebigen Startknoten) auf den vollständigen ungerichteten Graphen (d.h. von jedem Knoten existiert eine Kante zu allen anderen Knoten) mit 15 Knoten ausgeführt wird?
Ich verstehe das für den unmodifizierten Code so:
Für einen ungerichteten Graphen A,B,C (im Dreieck gezeichnet) wird der Startwert A gewählt. A wird auf true gesetzt. Anschließend werden aller Nachbarn von A untersucht, in diesen Fall B. Wenn ein Nachbar auf false gesetzt ist, wird DFS1 nochmals aufgerufen und somit wird auch B true. Im nächsten Schritt wäre dann C dran.
So weit so gut. Für den modifizierten Code, ändert sich doch kaum was außer das im letzen Schritt C wieder auf false gesetzt wird, weil A ja schon besucht wurde. Stimmt das so weit?
Wenn ich das dann richtig verstehe, wird
Code:
Discovered[u] <- false