[Algoritmi] Costo esecuzione visita DFS

[jJjjJ]

Ho un dubbio a proposito del costo di esecuzione di una visità in profondità di un albero implementata in questo modo:

Codice:

algoritmo DFS( nodo r )
       Pila S
       S.push( r )
       while( not S.isEmpty() ) do
              u <- S.pop()
              if( u != null ) then
                     visita u
                     S.push( figlio dx di u )
                     S.push( figlio sx di u )


Per quanto riguarda il costo temporale ho cercato di considerare il caso peggiore. L'albero che visitiamo ha, per ogni nodo, al più due figli. Supponiamo che l'albero T abbia esattamente $n$ allora il caso peggiore è quando $T$ degenera in lista, poiché in questo caso, per ogni nodo di $T$ si impilano due record ( eventualmente nulli ) su S. Da ciò otteniamo che la grandezza della pila è $2n$ nel caso peggiore e dunque le iterazioni del ciclo while sono $O( n )$ da cui $T_{w o r st} = O( n ) $

Per quanto riguarda lo spazio sempre con lo stesso caso peggiore si ha che $S( n ) = 2n$ da cui $S(n) = O(n)$

E' corretto?

[Cronovirus]

Io sapevo che se il grafo ha $n$ nodi e $m$ lati, allora il tempo è $\Theta (n+m)$

[Giova411]

Sì, si dice nell'ordine di grandezza O(n + m), ossia somma di nodi ed archi.
Ma parlavi di albero o grafo?

[Cronovirus]

Un albero... è un grafo

[Giova411]

Un albero... è un grafo

(grafo non orientato, connesso e privo di cicli)

[jJjjJ]

Come si dimostra?

[Cronovirus]

Come si dimostra?

Con google https://it.m.wikipedia.org/wiki/Ricerca_in_profondità

[jJjjJ]

Ma siete sicuri che non sia un'implementazione su un grafo? Sembra più la visita di un grafo tramite l'individuazione di sottoalberi. Io ho chiesto della visita in profondità di un albero, e infatti se guardate l'algoritmo da me postato è molto diverso anche concettualmente da quello di wikipedia. In ogni caso poi sto parlando di un albero con al più due figli per ogni nodo, e dunque il numero degli archi è al più $ n - 1$ quindi la mia delimitazione va bene anche usando le vostre...

[Cronovirus]

Non capisco il problema.. Il risultato che ti ho proposto e che poi ho visto essere anche su wikipedia è in generale sui grafi, poi se tu lo applichi ad un albero con al più n-1 archi è uguale. La dimostrazione che chiedevi è semplicemente applicare il tuo caso particolare a quello generale che ti ho proposto

[jJjjJ]

No perché i grafi non li abbiamo trattati e volevo vedere se potevo dimostrare come ho fatto io quel caso particolare...