# Anzahl der Rekursionsaufrufe eines DFS Algorithmus



## gamma21 (29. Mrz 2019)

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:

```
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  
	
	
	
	





```
Discovered[u] <- false
```
 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 
	
	
	
	





```
Discovered[u] <- false
```
 nur einmal aufgerufen und zwar dann, wenn alle Nachbarn besucht wurden.


----------



## mihe7 (29. Mrz 2019)

Im unmodifizierten Fall, wird jeder Knoten nur einmal besucht, z. B. A -> B und B -> C. Dann sind alle Knoten markiert. Wenn Du dagegen im letzten Schritt die Markierung aufhebst, werden Knoten mehrfach besucht.


```
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
    DFS1(G,B)
      B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C)
          C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
  (A,C): C visited -> NOP
```
vs


```
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
    DFS1(G,B)
      B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C):
          C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
          C <- unvisited
      B <- unvisited
  (A,C): C unvisited also
    DFS1(G,C)
      C <- visited
      (C,A): A visited -> NOP
      (C,B): B unvisited also
        DFS1(G,B)
          B <- visited
            (B,A): A visited -> NOP
            (B,C): C visited -> NOP
          B <- unvisited
```


----------



## gamma21 (30. Mrz 2019)

Verstehe...damit wäre das ganze dann eine Endlosschleife.


----------



## mihe7 (30. Mrz 2019)

Nein.


----------



## gamma21 (31. Mrz 2019)

Gut es ist keine Endlosschleife weil durch das foreach(u,v) die Anzahl der Aufrufe begrenzt ist. Gefragt ist ja jetzt, wie oft kein weiterer Rekursionsaufruf getätigt wird. Und die Rekursion wird ja jedesmal aufgerufen. Stimmt es dann, dass nie der Fall eintritt, dass kein weiterer Rekursionsaufruf getätigt wird.


----------



## mihe7 (31. Mrz 2019)

Nein, bei den NOP-Fällen oben erfolgt kein weiterer Aufruf


----------



## gamma21 (1. Apr 2019)

Aber nur dann wenn beide NOP sind also für 

```
(B,A): A visited -> NOP
(B,C): C unvisited also
```
erfolgt ja ein Aufruf nämlich für C. Ich sehe hier nur nicht, wie ich eine allgemeine Aussage treffen kann.


----------



## mihe7 (1. Apr 2019)

gamma21 hat gesagt.:


> Aber nur dann wenn beide NOP sind also für
> 
> ```
> (B,A): A visited -> NOP
> ...


Die Frage war, wie oft kein rekursiver Aufruf erfolgt. Wurde ein Knoten bereits besucht, erfolgt kein weiterer rekursiver Aufruf. Du kannst diese Prüfung auch zu Beginn der Rekursion durchführen, dann wird es vielleicht deutlicher:

```
(B,A): also
  DFS1(G,A)
    A visited also NOP
```
D. h. für die Aufruf DFS1(G,B) würde zwar ein rekursiver Aufruf erfolgen, für diesen Aufruf DFS1(G,A) jedoch nicht mehr.


----------



## mihe7 (1. Apr 2019)

Nachtrag: es ist eine Interpretationsfrage. 

```
foreach Kante (u, v) inzident zu u
    if !Discovered[v]
    DFS1(G,v)
    else
      anzahl++
```

vs.

```
called = false
foreach Kante (u, v) inzident zu u
    if !Discovered[v]
      DFS1(G,v); called = true
if !called
  anzahl++
```


----------



## gamma21 (1. Apr 2019)

Hmm jetzt kenn ich mich gar nicht mehr aus. 

```
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
DFS1(G,B)
```
Das ist mein 1. Rekursiver Aufruf.

```
B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C):
```
Das mein 2.

```
C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
          C <- unvisited
      B <- unvisited
  (A,C): C unvisited also
```
3.

```
DFS1(G,C)

      C <- visited

      (C,A): A visited -> NOP

      (C,B): B unvisited also
```
Hier mein 4.und jetzt mein

```
DFS1(G,B)
          B <- visited
            (B,A): A visited -> NOP
            (B,C): C visited -> NOP
          B <- unvisited
```
5.Rekursiver Aufruf.
Ich kann zwar aus dem zählen der Aufrufe feststellen, dass kein weiterer Aufruf erfolgt wenn der Knoten besucht wurde, aus dem Code sehe ich das aber nicht. 
P.S: Für 5 Aufrufe bei 6 Möglichkeiten wird die Rekursion nur einmal nicht aufgerufen.


----------



## mihe7 (1. Apr 2019)

DFS1 wird doch jedesmal nicht aufgerufen, wenn der betreffende Knoten bereits als besucht markiert wurde.



gamma21 hat gesagt.:


> aus dem Code sehe ich das aber nicht.


Selbstverständlich sieht man das:

```
if !Discovered[v]
        DFS1(G,v)
```
DFS1(G,v) wird nur aufgerufen, wenn v noch nicht discovered ist. Umgekehrt wird DFS1(G,v) nicht aufgerufen, wenn v bereits discovered ist.


----------



## gamma21 (1. Apr 2019)

Ja das stimmt. Wie kann ich nun aber eine allgemeine Aussage für 15 Knoten treffen?


----------



## mihe7 (1. Apr 2019)

Vielleicht mal als Baum:

```
A
       / \
      /   \
     /     \
    /       \
   B         C
  / \       / \
 /   \     /   \
A     C   A     B
=    / \  =    / \
    A   B     A   C
    =   =     =   =
```
Das = kennzeichnet die Stellen, an denen kein rekursiver Aufruf mehr erfolgt (sprich: die Blätter im Baum).


----------



## gamma21 (1. Apr 2019)

Also 1.einmal danke für deine Geduld und die guten Erklärungsversuche.
Das heißt es findet hier 6 mal kein rekursiver Aufruf statt. Ich denke (hoffe) es ist kein Zufall, dass es genau 3 Faktorielle sind. Für 15 Knoten wären es dann 15!. Das wäre 






 mal KEINE Rekursion. Bin mir nicht ganz sicher ob das so stimmt.


----------



## mihe7 (1. Apr 2019)

Gegeben sei ein vollständig verbundener Graph G mit n Knoten. Für jeden dieser n Knoten existieren n-1 ausgehende Kanten, die traversiert werden können. Beispiel für zwei Knoten A und B: A <==> B, A hat Kante zu B und B hat Kante zu A, d. h. jeder Knoten besitzt eine ausgehende Kante.

Im Baum B (wie in #13 gezeigt) hat jeder Knoten, der kein Blattknoten ist, dem Graphen G entsprechend n-1 Nachfolger. Im Beispiel oben haben wir drei Knoten A, B und C. Dabei hat A hat die Knoten B und C als Nachfolger, B hat die Nachfolger A und C usw. 

Besucht man nun einen Knoten, der kein Blattknoten ist, fallen für jeden seiner n-1 Nachfolger die rekursiven Aufrufe weg, die zu einem seiner Vorgänger führen. Mit jeder Ebene erhöht sich die Zahl der besuchten Knoten (= Vorgänger) um 1, womit sich gleichzeitig die Zahl der noch nicht besuchten Knoten um 1 verringert. Dies hat lediglich auf die Kanten der Wurzel keine Auswirkung. 

Bei n Knoten hat die Wurzel n-1 Nachfolger. Für jeden dieser n-1 Knoten fällt 1 rekursiver Aufruf weg, so dass noch n-2 rekursive Aufrufe übrig bleiben. Für jeden dieser n-2 rekursive Aufrufe gäbe es wieder n-1 Nachfolger, wovon jetzt aber 2 rekursive Aufrufe wegfallen (es gibt jetzt zwei Vorgänger), so dass noch n-3 rekursive Aufrufe übrig bleiben usw. Der Spaß wird wiederholt, bis gar kein rekursive Aufruf mehr erfolgt.

D. h. wir sparen (n-1)*1 + (n-1)*(n-2)*2 + (n-1)*(n-2)*(n-3)*3 + ... = sum_{i=1}^{n-1} i * (n-1)! / (n-1-i)! 

Für n=15: https://www.wolframalpha.com/input/?i=sum+i*(14!/(14-i)!),+i=1+to+14

Voraussetzung: ich habe mich nirgends vertan


----------



## gamma21 (3. Apr 2019)

Nachdem das Beispiel in der Übung gestern aufgelöst wurde, möchte ich die Antwort nun auch noch bekannt geben. Richtig wäre (zumindest laut Lösung) 14 Faktorielle gewesen, was sich aus den Baum Ergibt.


----------



## mihe7 (3. Apr 2019)

Dann wurden vermutlich alle eingesparten Aufrufe (und nicht nur die nicht aufgerufenen) gezählt. Müsste ich jetzt nachrechnen, habe ich jetzt aber keine Zeit.


----------

